Descriptions

Farmer John 让奶牛们找一些数加起来等于一个给出的数N。但是奶牛们只会用2的整数幂。下面是凑出7的方式

1) 1+1+1+1+1+1+1
2) 1+1+1+1+1+2
3) 1+1+1+2+2
4) 1+1+1+4
5) 1+2+2+2
6) 1+2+4

帮助FJ找到 N的分配数 (1 <= N <= 1,000,000).

Input

N

Output

排列方式总数。由于这个数可能很大，只需要保留最后9位

Sample Input

7

Sample Output

6

Hint

打表的会被系统自动识别判为WA

题解

dp[i]:i的二次幂划分方案数

• 如果i是奇数，在dp[i-1]方案的末尾插1，组合数没有增加
• 如果i是偶数，可以由奇数得到，只是在末尾插1，组合数没有增加；也可以由偶数 i/2 左移一位得到，组合数也没有增加,即dp[i]=dp[i−1]+dp[i/2]

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>
using namespace std;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
typedef pair<int,int> PII;
typedef long long LL;

const int N=1e6+10,mod=1e9;
int f[N];
int n;

int main()
{
    cin>>n;

    f[0]=1;
    for(int i=1;i<=n;i++)
        if(i & 1) f[i]=f[i-1];
        else f[i]=(f[i-1]+f[i/2])%mod;

    cout<<f[n]<<endl;
   // system("pause");
}