一个整数总可以拆分为 22 的幂的和。
例如：77 可以拆分成
7=1+2+4,7=1+2+2+2,7=1+1+1+4,7=1+1+1+2+2,
7=1+1+1+1+1+2,7=1+1+1+1+1+1+1
共计 66 种不同拆分方式。
再比如：44 可以拆分成：4=4,4=1+1+1+1,4=2+2,4=1+1+2
用 f(n)f(n) 表示 nn 的不同拆分的种数，例如 f(7)=6f(7)=6。
要求编写程序，读入 nn，输出 f(n)mod109f(n)mod109。
输入格式
一个整数 nn。
输出格式
一个整数，表示 f(n)mod109f(n)mod109。
数据范围
1≤N≤1061≤N≤106
输入样例：
7
输出样例：
6思路就是完全背包~
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int mod=1e9;
int f[N];///一个整数n的方案数
//背包容量为整数n物品的体积为1，2，4，8....
int main()
{
int n;
///int a[N];
while(cin>>n)
{
///完全背包
/* int cn=1;
for(int i=1;i<=n;i*=2)
{
a[cn++]=i;
}*/
memset(f,0,sizeof(f));
f[0]=1;
for(int i=1;i<=n;i*=2)///循环物品
{
for(int j=i;j<=n;j++)///循环背包 容量
{
///f[j]=f[j]+f[j-a[i]];
f[j]=(f[j]+f[j-i])%mod;
}
}
cout<<f[n]<<endl;
}
return 0;
}