给一个整数n, n<10^18,拆成若干段,每段加起来求和。输出所有和中 <= k 的个数。k<10^18。c++代码
时间: 2024-01-22 07:19:48 浏览: 25
这是一个动态规划问题,可以使用记忆化搜索或者递推来实现。
记忆化搜索:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 20;
long long n, k, dp[MAXN][MAXN][2];
long long dfs(int pos, int cnt, bool limit) {
if (pos == 0) {
return cnt == 0 ? 1 : 0;
}
if (!limit && dp[pos][cnt][0] != -1) {
return dp[pos][cnt][0];
}
long long ans = 0, max_digit = limit ? (n / (1ll << (pos - 1))) % 2 : 1;
for (int i = 0; i <= max_digit; ++i) {
ans += dfs(pos - 1, cnt - i, limit && (i == max_digit));
}
if (!limit) {
dp[pos][cnt][0] = ans;
}
return ans;
}
int main() {
cin >> n >> k;
memset(dp, -1, sizeof(dp));
int len = 0;
long long sum = 0, ans = 0;
while ((1ll << len) <= n) {
++len;
}
for (int i = len; i >= 1; --i) {
for (int j = 0; j <= len; ++j) {
if (j > sum) {
break;
}
long long tmp = dfs(i, j, (j == sum && i != len));
if (sum + (1ll << (i - 1)) * j + tmp > k) {
break;
}
sum += (1ll << (i - 1)) * j;
ans += tmp;
}
}
if (sum <= k) {
++ans;
}
cout << ans << endl;
return 0;
}
```
递推:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 20;
long long n, k, dp[MAXN][MAXN][2];
int main() {
cin >> n >> k;
memset(dp, 0, sizeof(dp));
int len = 0;
while ((1ll << len) <= n) {
++len;
}
dp[0][0][1] = 1;
for (int i = 1; i <= len; ++i) {
for (int j = 0; j <= len; ++j) {
for (int k = 0; k <= 1; ++k) {
long long ans = 0, max_digit = k ? (n / (1ll << (i - 1))) % 2 : 1;
for (int d = 0; d <= max_digit; ++d) {
ans += dp[i - 1][j - d][k && (d == max_digit)];
}
dp[i][j][k] = ans;
}
}
}
long long ans = 0, sum = 0;
for (int i = len; i >= 0; --i) {
for (int j = 0; j <= len; ++j) {
if (j > sum) {
break;
}
long long tmp = dp[i][j][(j == sum && i != len)];
if (sum + (1ll << (i - 1)) * j + tmp > k) {
break;
}
sum += (1ll << (i - 1)) * j;
ans += tmp;
}
}
if (sum <= k) {
++ans;
}
cout << ans << endl;
return 0;
}
```
相关推荐
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)