题解 | #整数拆分#

完全背包问题

代码

#include<iostream>
using namespace std;
const int mod=1e9,MAX=1e6+10;
int f[MAX];
int main(){
    int n;
    f[0]=1;
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i*=2){
            for(int j=i;j<=n;++j){
                f[j]=(f[j]+f[j-i])%mod;
            }
        }
        printf("%d\n",f[n]);
    }
    return 0;
}