AcWing 1081. 度的数量-分支代码等价变形-更好理解
原题链接
中等
作者:
现代修士o_O
,
2021-07-18 11:01:06
,
所有人可见
,
阅读 266
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 35;
int l, r, K, B;
int f[N][N];
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];
}
//求区间[0,n]中的 “满足条件的数” 的个数
//“满足条件的数”是指:一个数的B进制表示,其中有K位是1、其他位全是0
int dp(int n)
{
if (!n) return 0;//K > 0
vector<int> nums;//把n转成B进制存储
while (n) nums.push_back(n % B), n /= B;
int res = 0;//答案:[0,n]中共有多少个合法的数
int last = 0; //遍历当前位的时候,记录之前那些位已经占用多少个1,那么当前还能用的1的个数就是K-last
//从最高位开始遍历, 从低到高应该可以,就是数的个数表示稍微麻烦
for (int i = nums.size() - 1; i >= 0; i -- )
{
int x = nums[i]; //取当前位上的数
if (x == 1) // 左分支0, 右分支1
{
res += f[i][K - last];
last ++ ;
if (last > K) break;
}
else if (x > 1)//左分支0,1,右分支>1
{
res += f[i][K - last];
last ++ ;
res += f[i][K - last];//n能够表示成k个系数为1的b的幂次之和⟺n的b进制表示中恰好有k个1且其余位必须都是0
break;
}
if (i == 0 && last == K) res ++ ;//最后一个a0 x一定 == 0(ifelse过滤) 那last必然==K
}
return res;
}
int main()
{
init();
cin >> l >> r >> K >> B;
cout << dp(r) - dp(l - 1) << endl;
return 0;
}