Description
Farmer John commanded his cows to search for different sets of numbers that sum to a given number. The cows use only numbers that are an integer power of . Here are the possible sets of numbers that sum to : ) ++++++
) +++++
) ++++
) +++
) +++
) ++ Help FJ count all possible representations for a given integer N ( <= N <= ,,).
Input
A single line with a single integer, N.
Output
The number of ways to represent N as the indicated sum. Due to the potential huge size of this number, print only last digits (in base representation).
Sample Input
Sample Output
Source
如果i为奇数，肯定有一个1，把f[i-1]的每一种情况加一个1就得到fi,所以f[i]=f[i-1]
如果i为偶数，如果有1，至少有两个，则f[i-2]的每一种情况加两个1，就得到i，如果没有1，则把分解式中的每一项除2，则得到f[i/2]
所以f[i]=f[i-2]+f[i/2]
由于只要输出最后9个数位，别忘记模1000000000
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<cmath>
using namespace std;
#define N 1010006
#define MOD 1000000000
int n;
int dp[N];
void init(){ dp[]=;
dp[]=;
for(int i=;i<N;i++){
if(i&){
dp[i]=dp[i-];
}
else{
dp[i]=dp[i-]+dp[i/];
dp[i]%=MOD;
}
}
}
int main()
{
init();
while(scanf("%d",&n)==){ printf("%d\n",dp[n]); }
return ;
}