hdu 2709 递推

题意：给出一个数，把他拆成2^n和的形式，问有多少种拆法

链接：点我

对6进行分析

1 1 1 1 1 1

1 1 1 1 2

1 1 2 2

1 1 4

2 2 4

2 4

对最上面4个，显然是由4的拆分然后每个加+1 +1得到的

最下面是由，2的拆分乘2得到的

设a[n]为和为 n 的种类数；

根据题目可知，加数为2的N次方，即 n 为奇数时等于它前一个数 n-1 的种类数 a[n-1] ，若 n 为偶数时分加数中有无 1 讨论，即关键是对 n 为偶数时进行讨论：

1.n为奇数，a[n]=a[n-1]

2.n为偶数：

（1）如果加数里含1，则一定至少有两个1，即对n-2的每一个加数式后面 +1+1，总类数为a[n-2]；

（2）如果加数里没有1，即对n/2的每一个加数式乘以2，总类数为a[n-2]；

所以总的种类数为：a[n]=a[n-2]+a[n/2];

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<queue>

 #include<map>

 using namespace std;

 #define MOD 1000000000

 const int INF=0x3f3f3f3f;

 const double eps=1e-;

 typedef long long ll;

 #define cl(a) memset(a,0,sizeof(a))

 #define ts printf("*****\n");

 const int MAXN=;

 int a[MAXN];

 int n,m,tt;

 void init()

 {

     a[]=;

     a[]=;

     a[]=;

     for(int i=;i<MAXN;i++)

     {

         if(i%) a[i]=a[i-];

         else

         {

             a[i]=a[i/]+a[i-];

             a[i]%=MOD;

         }

     }

 }

 int main()

 {

     int i,j,k;

     #ifndef ONLINE_JUDGE

     freopen("1.in","r",stdin);

     #endif

     init();

     while(scanf("%d",&n)!=EOF)

     {

         printf("%d\n",a[n]);

     }

 }