题解 | #整数拆分#

#include <iostream>

using namespace std;

const int N = 1000010;
int dp[N];

int main(){
    //奇数:dp[n]=dp[n-1]
    //偶数:dp[n]=dp[n-1]+dp[n/2]
    int n;
    cin>>n;
    dp[0]=1;
    for(int i=1;i<=n;i++){
        if(i%2)dp[i]=dp[i-1];
        else{
            dp[i]=(dp[i-1]+dp[i/2])%1000000000;
        }
    }
    cout<<dp[n]<<endl;
    return 0;
}