Amount of Degrees

---

题意: 给你两个数 X,Y(X<=Y<2^31-1), 以及 k,b, 求所有的 i∈[X,Y] 的数目,i 在 b 进制下只由 b 个１和若干个０组成。注意有多组数据。

如 X=15,Y=20,k=2,b=2, 则会有：

17 = 2⁴+2⁰,
18 = 2⁴+2¹,
20 = 2⁴+2².

所以答案为３

---

分析：由于 X,Y 的范围较大，且数据组数较多，所以我们应该考虑有没有复杂度在 logn 级别的算法。

先来看看朴素算法：我们可以枚举每一个由 k 个１组成的 b 进制数，由于 X 最多有 log_bX 位，每一位可以选择取 0 或者１, 所以我们可以做到 O(2^log_bX) 左右的复杂度。但是当 b 比较小，如２或者３时，这种算法的弊端就显露出来了：我们对于每一位放１还是０都做了很多次判断。

所以我们想到了用动态规划。

先考虑二进制的１情况：如果用 f[i][j] 表示 i 位二进制数中出现 j 个１的数的数量，则 f[i][j]=f[i-1][j]+f[i-1][j-1], 分别为第 i 位放０和放１的状态转移。所以我们可以很轻松地预处理出 f 数组，f 数组只需要有 32*32 个元素即可满足题目的数据要求。接着对于 X 每一位为１的，ans 加上对应的 f 的值。过程大概是这样的：

比如对于二进制数 100110，求小于他的有２个１的数的个数
如果左数第一位为０，则 ans+=f[5][2]
如果第一位为１，那么继续讨论 1xxxxx
->如果第二位为０（第二位只能为０）那么继续讨论 10xxxx
->->如果第三位为０（第三位只能为０）那么继续讨论 100xxx
->->->如果第四位为０，由于现在在讨论 1000xx，所以 xx 中只需要有１个 x 为１，100xx 都可以构成与之前讨论得出的答案不同的答案，所以 ans+=f[2][1]
->->->如果第四位为１，那么继续讨论 1001xx,
->->->->如果第５位为０，那么 ans+=f[1][0],
->->->->由于第５不可以为１(为１的话就是 10011x, 永远无法满足题意)，所以直接略过，至此 ans 为所求。

代码大概是这样的：

ll work()
{
    int tot=0,one=0;
    for(int i=MX-1;i>=0;i--)            //从高位向低位推进
    {
        if(num[i+1])                            //num 即为处理中的数
        {
            tot+=f[i][k-one],one++; //one 是已经出现了几个１
            if(one>k)break;                 //如果已经出现了 k 个以上的１，不用继续累加了
        }
        if(i==0&&k==one)tot++;  //如果 num 自己就是一个满足要求的数，则 tot 自加
    }
    return tot;

由于本人第一次打数位 Dp, 代码又臭又长，已自裱千遍

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define MX 32
typedef long long ll;

using namespace std;

long long k,b;
int f[MX+1][MX+1], num[MX+1];

void init()
{
    f[0][0]=1; 
    for (int i=1;i<=32;++i) {
        f[i][0]=1; 
        for (int j=1;j<=i;++j) f[i][j]=f[i-1][j]+f[i-1][j-1];
    }
}

ll work()
{
    int tot=0,one=0;
    for(int i=MX-1;i>=0;i--)
    {
        if(num[i+1])
        {
            //cout<<i<<" "<<k-one<<endl;
            tot+=f[i][k-one],one++;
            if(one>k)break;
        }
        if(i==0&&k==one)tot++;
    }
    return tot;
}

void convert(ll x)
{
    ll tot=0;
    memset(num,0,sizeof(num));
    for(int i=1;i<=MX;i++)num[i]=x%b,x/=b;
    for(int i=MX;i>=1;i--)if(num[i]>=2)for(int j=i;j>=1;j--)num[j]=1;
}

int main()
{
    ll x,y;
    init();
    while(~scanf("%lld%lld%lld%lld",&x,&y,&k,&b))
    {
        int ans1,ans2;
        convert(x-1);
        ans1=work();
        convert(y);
        ans2=work();
        cout<<ans2-ans1<<endl;
    }
    return 0;
}