51nod 1383 母函数

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1383

一眼望去，不就是硬币兑换吗，母函数或者dp，直接暴力dp就A了，不过挺耗时的，有个方程可以O(N),

if(N%2==0) F[N]=F[N-1]+F[N>>1]

else F[N]=F[N-1]

对于一个偶数，可以让比他小一数的方案全部加一个'1'得到，也可以让比他小一半的数的方案元素都乘以2得到。

对于奇数只能由比他小的数加一得到。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define LL long long
 4 #define inf 0x3f3f3f3f
 5 LL mod=1e9+7;
 6 LL dp[1000005];
 7 LL a[25];
 8 int main()
 9 {
10     int N,i,j;
11     for(LL i=0;i<=20;++i) a[i]=(1<<i);
12     cin>>N;
13     dp[0]=1;
14     for(i=0;i<20;++i)
15     {
16         for(j=a[i];j<=N;++j)
17             dp[j]=(dp[j]+dp[j-a[i]])%mod;
18     }
19     cout<<dp[N]<<endl;
20     return 0;
21 }