兩種情況

1.n為奇數，則一定有一個1，所以a[n]=a[n-1]

2.n為偶數，如果加數里含1，則一定至少有兩個------>a[n-2]

???????????????如果加數里沒有1，則結果等于------------>a[n/2]

???????????????所以a[n]=a[n-2]+a[n/2]

代碼如下：

?

Code
#include<stdio.h>
__int64?a[1000002];
void?process()
{
????int?i;
????a[1]=1;a[2]=2;
????for(i=3;i<1000001;i++)
????{
????????if(i%2==0)
????????????a[i]=a[i-2]+a[i/2];
????????else
????????????a[i]=a[i-1];
????????a[i]%=1000000000;
????}
}
int?main()
{
????__int64?n;
????process();
????while(scanf("%I64d",&n)!=EOF)
????????printf("%I64d\n",a[n]);
????return?0;


}

轉載于:https://www.cnblogs.com/pandy/archive/2008/11/22/1339067.html

總結

以上是生活随笔為你收集整理的pku2229--sumsets(zjgsu,分花)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。