题解

其中的奇数都和前一个偶数一样，而偶数dp[i] = dp[i-1] + dp[i/2]; 解释如下: 10 中1开头的恰好都是9中的数列，不是1开头的最后那几行因为都是偶数，除以二以后恰好都是5中的数列。所以dp[10] = dp[9] + dp[5]； 以此类推：dp[i] = dp[i-1] + dp[i>>1]；

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
long long dp[1000000+20];
int main(){
    cin>>n;
    dp[1] = 1;dp[2] = 2;
    for(int i=3;i<=n;i++){
        if((i & 1) == 1)
            dp[i] = dp[i-1];
        else dp[i] = dp[i-1] + dp[i>>1];
        dp[i] %= 1000000000;
    }
    cout<<dp[n]<<endl;
    return 0;
}