AcWing 1081. 度的数量
原题链接
中等
作者:
静静在Coding
,
2022-04-03 11:25:18
,
所有人可见
,
阅读 149
非常细致
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 35;
int f[N][N];
int l,r,k,B;
void init()
{
for(int i = 0;i < N;i++){
for(int j = 0;j <= i;j++){
if(!j) f[i][j] = 1;
else f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
}
}
}
int dp(int num)
{
if(!num) return 0;
vector<int> a;
while(num) a.push_back(num%B),num/=B;
//for(int i = 0;i < n;i++)
//左分支选0到a[i] - 1,右分支选a[i]
int res = 0,acc = 0; //acc前面的1的个数
for(int i = a.size() - 1;i >= 0;i--){
if(a[i] == 0){
//只能进入为右分支 只能选0
}else if(a[i] == 1){
//左分支选0 右分支选1
//左分支方案数 选第i位为0 则后i位选k - acc位1;e3ed
res += f[i][k - acc];
//进入右分支 即选第i位位1进入右分支 即进入下一层
acc++;
//不能进入右分支
if(acc > k) break;
}else if(a[i] >= 2){
//左分支可以选0和1 右分支可以选a[i](不能进入右分支)
//左分支 选0 和选 1;
//左分支 选0
res += f[i][k - acc];
//左分支 选1
//如果不能选1 直接break;
if(acc + 1 > k) break;
res += f[i][k - acc - 1];
//右分支不合法 无法进入 即无法向下枚举
break;
}
//一直进入累加都是第i位是0的数,但是res += f[i][k - acc]
//其实f[i][k - acc] = 0 因为k - acc > i
//没有算上111111……全是1的数 要加上这个特例
if(!i && acc == k) res++;
}
return res;
}
int main()
{
cin>>l>>r>>k>>B;
//cout<<l<<r<<endl;
init();
cout<<dp(r) - dp(l - 1);
return 0;
}