POJ2229 Sumsets

題目連結：http://poj.org/problem?id=2229

解題思路：

其實這題也能有母函數做，隻不過資料量太大了，超了時，不信，你用1000000.跑跑看，多長時間才能出結果。

是以這題隻能找規律了。

如果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即可。

AC代碼：

#include<iostream>
#include<cstdio>
using namespace std;

int a[1000010];

int main()
{
    int i,n;
    a[1]=1;a[2]=2;
    for(i=3;i<=1000000;i++)
    {
        if(i&1)
            a[i]=a[i-1];
        else
            a[i]=(a[i-2]+a[i/2])%1000000000;
    }
    while(scanf("%d",&n)!=EOF)
        printf("%d\n",a[n]);
    return 0;
}
           

逾時代碼：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MOD=1000000000;
int c1[1000010],c2[1000010];

int main()
{
    int a[]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576};
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int i,j,k;
        memset(c1,0,sizeof(c1));
        memset(c2,0,sizeof(c2));
        for(i=0;i<=n;i++)
            c1[i]=1;
        for(i=1;a[i]<=n;i++)
        {
            for(j=0;j<=n;j++)
                for(k=0;k+j<=n;k+=a[i])
                    c2[j+k]=(c2[j+k]+c1[j])%MOD;
            for(j=0;j<=n;j++)
            {
                c1[j]=c2[j];
                c2[j]=0;
            }
        }
        printf("%d\n",c1[n]);
    }
    return 0;
}