题解 | #整数拆分#

#include <iostream>
using namespace std;
#define MAXN 1000001
int main(){
    long long N=0;
    cin>>N;
    //dp数组初始化
    int dp[MAXN]={0};
    dp[1]=1;
    for(int i=2;i<=N;i++){
        if(i%2==0){//i为偶数
            dp[i]=(dp[i-1]+dp[i/2])%1000000000;//拆分为包含1（1的个数一定为偶数个）和不含1的两种情形
        }
        else{//i为奇数
            dp[i]=dp[i-1]%1000000000;
        }
    }
    cout<<dp[N]<<endl;
}