题意：求（x--y）区间转化为b进制以后， 1 的个数为 k 的数的出现次数，并且其余位上的数必须为0。
原题要求的是k个不同b次幂相加得到的不同的数的个数，所以每一位上的的数不能出现除1和0以外的数，有了这样一个转换就好办了。
数位dp，枚举时只枚举含0,1的位，一定是从高位枚举，设d[pos][num1][sum][dig]为从pos到最低位，1出现次数为num1时，要求出现sum次，dig进制下数的个数。
注意前导0的判断，几乎是模板题，写法都差不多。
#include <iostream> #include <cstdio> #include <ctime> #include <cstring> #include <algorithm> #include <vector> #include <map> #include <cmath> #include <set> #include <queue> using namespace std; typedef unsigned long long ll; const int INF=1e9+100; const int mod=1e9+7; int d[50][50][25][15],f[50]; int x,y,k,b; int dfs(int pos,int num1,int sum,int dig,int limit,int lead){ if(pos==-1){ if(num1==sum) return 1; else return 0; } if(!lead&&!limit&&d[pos][num1][sum][dig]!=-1) return d[pos][num1][sum][dig]; int up=limit?f[pos]:1; int ans=0; for(int i=0;i<=up&&i<=1;i++){ if(i==1){ ans+=dfs(pos-1,num1+1,sum,dig,limit&&i==up,0); }else{ if(lead){ ans+=dfs(pos-1,num1,sum,dig,limit&&i==up,1); }else{ ans+=dfs(pos-1,num1,sum,dig,limit&&i==up,0); } } } if(!limit&&!lead) d[pos][num1][sum][dig]=ans; return ans; } int solve(int n){ int pos=0; while(n){ f[pos++]=n%b; n/=b; } return dfs(pos-1,0,k,b,1,1); } int main(){ //freopen("out.txt","w",stdout); memset(d,-1,sizeof(d)); while(scanf("%d %d",&x,&y)!=EOF){ scanf("%d %d",&k,&b); printf("%d\n",solve(y)-solve(x-1)); } return 0; }