题目描述：
一个整数总可以拆分为 $ 2 $ 的幂的和。
例如： $ 7 $ 可以拆分成
共计 $ 6 $ 种不同拆分方式。
再比如： $ 4 $ 可以拆分成：
用 $ f(n) $ 表示 $ n $ 的不同拆分的种数，例如 $ f(7)=6 $ 。
要求编写程序，读入 $ n $ ，输出 $ f(n)\mod10^9 $ 。
输入格式
一个整数 $ n $ 。
输出格式
一个整数，表示 $ f(n)\mod10^9 $ 。
数据范围
$ 1 \le N \le 10^6 $
输入样例：
输出样例：
题解：
完全背包做法：
可以把 $ n $ 看做背包容量，那么有 $ \log_2(n) $ 个物品 $ 1, 2, 4, 8, \cdots $ ，每个物品都是无限的，就是个完全背包，不过完全背包是求最大值的。
发现是从上一行的该列和上一行的前几列转移过来的。可以使用一维数组优化
因为无限取，需要顺序枚举。
该题目是求方案数，可以对方程修改为相加即可。
从前往后枚举
递推做法：
可以发现，如果是奇数的话，和前一个偶数是相等的。
如果是偶数的话，
- 偶数首先可以分为 $ 1 $ 加一个奇数，方案数是等于奇数拆分的方案数，这是包含 $ 1 $ 的拆分。
- 不包含 $ 1 $ 的拆分，最小的拆分值为 $ 2 $ ，不可能会出现奇数。因此刚好等于奇数 $ \frac{n}{2} $ 的方案数。
代码：
完全背包
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| using namespace std;
using namespace FAST_IO;
const ll mod = 1e9;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e6 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
ll dp[maxn];
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
dp[0] = 1;
cin >> n;
for (int i = 1; i <= n; i *= 2)
{
for (int j = i; j <= n; j++)
{
dp[j] = (dp[j] + dp[j - i]) % mod;
}
}
cout << dp[n] << endl;
return 0;
}
|
直接递推
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| using namespace std;
using namespace FAST_IO;
const ll mod = 1e9;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e6 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
ll dp[maxn];
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
dp[0] = 1;
cin >> n;
for(int i = 1; i<= n; i++)
{
dp[i] = (dp[i - 1] + (!(i & 1)) * dp[i / 2]) % mod;
}
cout << dp[n] << endl;
return 0;
}
|