1.题目描述： 2.题意： 给你一个区间[X,Y]，计数区间中所有由K个不同的B的幂的和组成的数字的个数。
3.思路： 数位dp。 题意说白了：计数B进制下，数字由K个1其余都是0组成的数字的个数。
4.代码：
//F #include<bits/stdc++.h> #define rep(i,a,b) for(int i=(a);i<(b);++i) #define mem(a,b) memset(a,(b),sizeof(a)) using namespace std; typedef long long ll; int l,r,k,b; int dig[50]; int dp[50][50]; int dfs(int pos,int cnt,bool lim) { if(!pos) return cnt==k; if(!lim&&~dp[pos][cnt]) return dp[pos][cnt]; int up=lim?(dig[pos]?1:0):1,res=0; rep(i,0,up+1) res+=dfs(pos-1,cnt+i,lim&&i==dig[pos]); if(!lim) dp[pos][cnt]=res; return res; } int work(int n) { int pos=0; while(n) dig[++pos]=n%b,n/=b; return dfs(pos,0,1); } inline void solve() { mem(dp,-1); printf("%d",work(r)-work(l-1)); } int main() { while(~scanf("%d%d%d%d",&l,&r,&k,&b)) solve(); return 0; }