看《浅谈数位类统计问题》论文写的，感觉分析还是相当的到位啊。
一个数分解成进制数相加，该位置上的数绝对为1.
代码：
View Code
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 using std::min; 6 using std::swap; 7 int const N = 40; 8 int f[N][N],num[N],top,x,y,b,k,s,tot; 9 void pre() 10 { 11 f[0][0]=1; 12 for(int i=1;i<=31;i++) 13 { 14 f[i][0]=f[i-1][0]; 15 for(int j=1;j<=i;j++) 16 f[i][j]=f[i-1][j]+f[i-1][j-1]; 17 } 18 } 19 int getsum(int x,int b) 20 { 21 tot=s=top=0; 22 while(x) 23 { 24 num[top++]=x%b; 25 x/=b; 26 } 27 for(int i=top-1;i>=0;i--) 28 { 29 if(!s&&num[i]>0)s=i; 30 if(num[i]>1) 31 { 32 while(i>=0)x^=(1<<i),i--; 33 break; 34 } 35 if(num[i]==1) 36 { 37 x^=(1<<i); 38 } 39 } 40 int ret=0; 41 s++; 42 s=min(31,s); 43 for(;s>0;s--) 44 { 45 if(x&(1<<s)) 46 { 47 tot++; 48 if(tot>k)break; 49 x^=(1<<s); 50 } 51 if((1<<(s-1))<=x) 52 { 53 ret+=f[s-1][k-tot]; 54 } 55 } 56 if(tot+x==k)ret++; 57 return ret; 58 } 59 int main() 60 { 61 pre(); 62 while(~scanf("%d %d %d %d",&x,&y,&k,&b)) 63 { 64 if(x>y)swap(x,y); 65 printf("%d\n",getsum(y,b)-getsum(x-1,b)); 66 } 67 return 0; 68 }