AcWing 3382. 整数拆分
原题链接
简单
作者:
zhaoxi
,
2022-02-24 22:21:33
,
所有人可见
,
阅读 174
/*
这和算法基础课中讲的完全背包问题的第二题不同的是,这个题要求它的矩阵只能是2的幂
并且和上一题北大上机考试类似的都是求选法的个数,在这方面是一样的思路,
只不过在进行状态方程的计算的时候,
f[i,j] = f[i-1,j]+f[i-1,j-v]+.........f[i-1,j-k*v]
利用f[i,j-v] = f[i-1,j-v]+f[i-1,j-2v]+f[i-1,j-3v]+.....+f[i-1,j-k*v]
因此就得到f[i,j]=f[i-1,j]+f[i,j-v];
*/
#include <iostream>
using namespace std;
const int N = 1e6 + 10, MOD = 1e9;
int f[N];
int v[N];
int n;
int main() {
cin >> n;
int V = n;
int cnt = 0, m = 1;
while (m <= n) {
v[++ cnt] = m;
m *= 2;
}
n = cnt;
f[0] = 1;
for (int i = 1; i <= n; i ++) {
for (int j = v[i]; j <= V; j ++) {
f[j] = (f[j] + f[j - v[i]]) % MOD;
}
}
cout << f[V] << endl;
return 0;
}