bzoj1677[Usaco2005 Jan]Sumsets 求和*

bzoj1677[Usaco2005 Jan]Sumsets 求和

题意：

给出一个N，使用一些2的若干次幂的数相加来求之．问有多少种方法。N≤1000000。

题解：

可以写完全背包，然而排名会倒数~正解是一个递推式：

f[i]=f[i-1]，i为奇数，f[1]=1

f[i-1]+f[i/2]，i为偶数

神犇们的证明我没看懂QAQ。

代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define inc(i,j,k) for(int i=j;i<=k;i++)
 5 #define maxn 1000001
 6 #define mod 1000000000
 7 using namespace std;
 8 
 9 int n,f[maxn];
10 int main(){
11     scanf("%d",&n); f[1]=1;
12     inc(i,2,n){f[i]=f[i-1]; if(!(i&1))f[i]=(f[i]+f[i>>1])%mod;}
13     printf("%d",f[n]); return 0;
14 }

20160804