题目链接: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;
}