分析
dp(x)
表示从 $0-x$ 满足题意的数的个数。
那么接下来分情况讨论以分解问题:(设 $x$ 有 $n$ 位,在这里我们记最高位对应下标为 $n-1$, 个位是 $0$ ,同时记当前已经放了last
个 $1$ (那么当前还可以放置 k-last
个 $1$))
设当前位对应的下标是 $i$
-
如果当前位是 $0$ ,那么它不会对 $1$ 的个数造成任何影响,直接跳过。
-
如果当前位 $>1$ (例如 $i$ 和后面的数位组成了串 $2488$ 那我们的任务则是求出 $0-2488$ 有几个符合题意(因为前面数位的贡献已经统计好了)),那么相当于你有长度为 $i+1$ 的串,只需从中选取
k-last
个 $1$ 即可,对应的贡献为 $C_{i+1}^{k-last}$ -
如果当前位是 $1$ 例如 $i$ 和后面的数位组成了串 $1488$ 那我们的任务则是求出 $0-1488$ 有几个符合题意(因为前面数位的贡献已经统计好了),可以看出 $0-999$ 的部分的贡献是 $C_{3}^{k-last}$ ,而 $1000-1488$ 的部分不易于在当前状态算出,故考虑转移到下一位继续统计,转移的时候
last++
,因为当前位是 $1$,在当前位放置了一个 $1$ 。
这样我们便可以一层一层地向下计算下去了。
注意,在上图粉色部分是最后没有统计的,需要特殊考虑一下。
个人心得:做数位DP要时刻记得自己是对整个区间的数进行考虑,而不是单个数,并且在解题的时候要保证合理分划状态,保证统计时候的正确性。
代码:
#include<bits/stdc++.h>
using namespace std;
const int N=35;
//预处理求出组合数
int c[N][N];
void init(){
for(int i=0;i<=N;i++)
for(int j=0;j<=i;j++)
if(!j) c[i][j]=1;
else c[i][j]=c[i-1][j-1]+c[i-1][j];
}
int k,b;
int l,r;
int dp(int n){
if(!n) return 0;
vector<int> nums;
while(n) nums.push_back(n%b),n/=b; //用nums储存b进制下的数码
int res=0,last=0;
for(int i=nums.size()-1;~i;i--){
int x=nums[i]; //这里的x指n的最高位是 x
//核心部分,开始分情况讨论
if(x) //x>=1
{
if(x==1){
if(k>=last) res+=c[i][k-last];
last++;
if(last>k) break;
}else{
if(k>=last) res+=c[i+1][k-last];
break;
}
}
if(i==0 && k==last) res++; //如果到了最后一位
}
return res;
}
int main(){
init();
cin>>l>>r>>k>>b;
cout<<dp(r)-dp(l-1)<<endl; //类似于前缀和的思想
return 0;
}