C++UVALive 4864 Bit Counting –记念化搜索 / 数位DP?

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;

int Count(ll state) {
    int cnt = 0;
    while(state) {
        if(state & 1LL) cnt++;
        state >>= 1;
    }
    return cnt;
}
int WEI(ll state) {
    int cnt = 0;
    while(state) {
        cnt++;
        state >>= 1;
    }
    return cnt;
}
ll C[100][100];
int in[67];

void init()
{
    C[0][0] = 1;
    for(int i = 1; i < 90; i++) {
        C[i][0] = 1;
        for(int j = 1; j <= i; j++) {
            C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
        }
    }
    memset(in,0,sizeof(in));
    in[1] = 0;
    for(int i=2;i<=61;i++)
        in[i] = in[Count(i)]+1;
}
int X;

ll get(ll state,int cnt) {
    if(state < 0) return 0;
    int len = WEI(state);
    if(len < cnt) return 0;   // not enough
    if(cnt == 0)  return 1;   // no demand
    return get(state-(1LL<<(len-1)),cnt-1) + C[len-1][cnt];
}

ll getsum(ll R,ll L) {
    ll ans = 0;
    for(int i=1;i<=61;i++)
        if(in[i]+1 == X) ans += get(R,i)-get(L-1,i);
    return ans;
}

int main()
{
    init();
    int i,j;
    ll L,R;
    while(scanf("%lld%lld%d",&L,&R,&X)!=EOF && L+R+X)
    {
        ll ans = 0;
        if(X == 0 && L == 1LL) { puts("1"); continue; }
        if(X == 1 && L == 1LL) ans--;  //1's binary code is 1, but 1 is not in (X==1)
        ans += getsum(R,L);
        cout<<ans<<endl;
    }
    return 0;
}

C++ 1C++ 2

代码:

对于二进制来说,能够如此搜索出来:

2.此处放0:那么前边就不管放了,为C[5][k]

题材链接: 难点链接

题意:如若2个数二进制n有k位1,那么f1[n]
= k,要是k有s位二进制1,那么f2[n] = f1[k] = s.
 如此往返,直到fx[n] =
1,此时的x便是n的”K值“,今后供给[L,R]内的”K值“为X的数有稍许个。(1<=L<=福睿斯<=10^18)

从而这么递归的探寻就可得出答案,也得以用DP做。

下一场就将求[L,R]里面包车型客车个数变成求[1,R]-[1,L-1],所以大家只需数出对于各样数n,[1,n]里头有稍许个数的”K值“为X即可。

View Code

1.此处放1:那么就卓殊求<=1001时放k-1个1的数的个数

 

解法:首先能够见见10^18最三唯有61位左右的数,所以大家只需处理1~61之间各个数有多少个1,即可见道1~61之间各类数”K值“是稍稍。

比如说<=101001,要知足有k个1的数的个数,那么大家从高位往低位扫,扫到第3个1,那么今后有二种情状: