#10163. 「一本通 5.3 例 1」Amount of Degrees - 题目 - LibreOJ (loj.ac)
题目描述
求给定区间 中满足下列条件的整数个数：这个数恰好等于 个互不相等的 的整数次幂之和。
例如，设 ，则有且仅有下列三个数满足题意：
17&=2^4+2^0 \\ 18&=2^4+2^1 \\ 20&=2^4+2^2 \end{align} $$ ### 输入格式 第一行包含两个整数 X 和 Y，接下来两行包含整数 K 和 B。 ### 输出格式 只包含一个整数，表示满足条件的数的个数。 ### 样例 input ```c 15 20 2 2 ``` output ```c 3 ``` ### 数据范围与提示 对于全部数据，$1\le X\le Y\le 2^{31}-1,1\le K\le 20,2\le B\le 10$。 ## 思路 当$B=2, k=2$时, 其实也是求二进制中包含两个1的数, 如： ```c++ 15: 01111 16: 10000 17: 10001 18: 10010 19: 10011 20: 11000 ``` 显然17,18,20包含两个1, 是最终答案。 于是问题转化为求区间$[x,y]$中以$B$进制表示后非0项为$K$的数的个数。 数位DP 技巧1：求`[x,y]`区间时可以定义状态`f[i]`为`1~i`, 就可以用 `f[y]-f[x-1]`来表示。 技巧2：考虑时尽量使用树的结构来考虑 例如一个数n![[07 - ARCHIVES/知识库/计算机/软件工程/操作系统/CSAPP/第1章 计算机系统漫游/图片/Pasted image 20221225133936.png]] 而求组合数可以使用一层优化[[求组合数#ab--2000|a,b <= 2000]], 这里a,b是转化为B进制后的位数。 ## 代码 ```c++ const int N = 35; int 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 - 1] + f[i - 1][j]; } } int dp(int u) { if (!u) return 0; vector<int> nums; while (u) nums.push_back(u % B), u /= B; int res = 0; int last = 0; for (int i = nums.size() - 1; i >= 0; i--) { int x = nums[i]; if (x) // 计算左分支 { res += f[i][K - last]; // 当前位为0时 if (x > 1) // 若当前位可以大于等于1 { if (K - last - 1 >= 0) res += f[i][K - last - 1]; break; } else // 说明当前位除了0之外只能为1, 即为最大值 { last++; if (last > K) break; } } if (!i && last == K) res++; } return res; } int main() { init(); int l, r; cin >> l >> r >> K >> B; cout << dp(r) - dp(l - 1) << endl; return 0; } ```