题意：统计区间内t=B^n+.....+B^0,每项系数都为0或1，统计1的个数恰好为1的情况，这样的数有多少个
分析：看的刘聪的论文，分析很好，http://pan.baidu.com/s/1pL4FF4n，转化为统计二叉树上1的个数代码写的有点糙
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=55; 4 typedef long long ll; 5 ll f[maxn][maxn],d[maxn]; 6 int b,k; 7 void init(){ 8 for(int i=0;i<=31;i++){ 9 f[i][0]=1; 10 for(int j=1;j<=i;j++) 11 f[i][j]=f[i-1][j]+f[i-1][j-1]; 12 } 13 } 14 15 ll cal(ll x){ 16 int tot=0;ll ret=0; 17 for(int i=31;i>0;i--){ 18 if(x&((ll)1<<i)){ 19 ++tot; 20 if(tot>k)break; 21 } 22 if(x&(1<<(i-1))) 23 ret+=f[i-1][k-tot]; 24 } 25 if(tot+x==k)++ret; 26 return ret; 27 } 28 29 ll solve(ll x){ 30 if(b==2)return cal(x); 31 memset(d,0,sizeof(d)); 32 int len=0; 33 while(x>0){ 34 d[len++]=x%b; 35 x/=b; 36 } 37 int id=len-1; 38 while(id>=0&&d[id]<2)id--; 39 for(int i=0;i<=id;i++)d[i]=1; 40 ll tmp=0,q=1; 41 for(int i=0;i<len;i++){ 42 tmp+=d[i]*q; 43 q*=2; 44 } 45 return cal(tmp); 46 } 47 48 int main(){ 49 init();ll x,y; 50 while(cin>>x>>y>>k>>b) 51 cout<<solve(y+1)-solve(x-1)<<endl; 52 53 return 0; 54 }