对于 的分数，考虑到n不大，所以我们可以直接找出所有2的幂次方的数，然后跑完全背包，复杂度应该是级别
#include <iostream>
using namespace std;
int a[25];
long long dp[10000005];
int main() {
int n;
cin >> n;
int p = 1;
int cnt = 0; //物品数量
for (int i = 0; p <= n; i++) { //求物品
cnt++;
a[i] = p;
p *= 2;
}
dp[0] = 1; //预处理
for (int i = 0; i < cnt; i++) { //注意是i<cnt
for (int j = a[i]; j <= n; j++) { //完全背包正着循环
dp[j] += dp[j - a[i]];
dp[j] %= 1000000000; //取模
}
}
cout << dp[n] << endl; //输出
return 0; //华丽的结束
}
对于 的数据，其实发现奇数只能通过偶数 +1 得到，而偶数可以通过奇数 +1 ，也可以通过其折半的偶数翻倍得来，因此得到方程
#include <bits/stdc++.h>
using namespace std;
long long s[10000001];
#define N 1000000000
int i, j, k, n;
int main() {
cin >> n;
j = 1;
k = 1;
s[0] = 1;
for (i = 1; i <= n; i++) {
if (i % 2 == 1)
s[i] = s[i - 1];
else
s[i] = (s[i - 1] + s[i / 2]) % N;
}
cout << s[n];
return 0;
}