求从L~R转换成B进制之后数位之和为M的数有多少个。
国家集训队09年的论文《浅谈数位类统计问题》对这一类的问题总结的比较详细，数形结合的思想十分巧妙。
第二种查询要用到第一种查询的结果，然后二分一下就可以了。
1 #include <string.h> 2 #include <stdio.h> 3 #include <string.h> 4 typedef long long LL; 5 int q,x,y,b,m,k; 6 int d[32][301],num[32]; 7 int dp(int l,int s){ 8 if(s<0)return 0; 9 if(l==-1)return s==0; 10 if(d[l][s]!=-1)return d[l][s]; 11 d[l][s]=0; 12 for(int i=0;i<b;i++) 13 d[l][s]+=dp(l-1,s-i); 14 return d[l][s]; 15 } 16 int getsum(int x){ 17 if(x<0)return 0; 18 int len=0,ans=0,kk=m; 19 while(x)num[len++]=x%b,x/=b; 20 for(int i=len-1;i>=0;i--){ 21 for(int j=num[i];j>0;j--){ 22 ans+=dp(i-1,kk),kk--; 23 } 24 } 25 return ans+(kk==0); 26 } 27 int main(){ 28 int cas=0; 29 while(scanf("%d%d%d%d%d",&q,&x,&y,&b,&m)!=EOF){ 30 if(x>y)x^=y^=x^=y; 31 memset(d,-1,sizeof d); 32 int lt=getsum(x-1),rt=getsum(y); 33 printf("Case %d:\n",++cas); 34 if(q==1)printf("%d\n",rt-lt); 35 else{ 36 scanf("%d",&k); 37 if(rt-lt<k){ 38 printf("Could not find the Number!\n"); 39 continue; 40 } 41 int min=x-1,max=y,mid=((LL)min+max)>>1; 42 for(;min!=mid;mid=((LL)min+max)>>1){ 43 if(getsum(mid)-lt<k)min=mid; 44 else max=mid; 45 } 46 printf("%d\n",mid+1); 47 } 48 49 } 50 return 0; 51 }