题目描述：

一个整数总可以拆分为2的幂的和，例如：

7=1+2+4

7=1+2+2+2

7=1+1+1+4

7=1+1+1+2+2

7=1+1+1+1+1+2

7=1+1+1+1+1+1+1

总共有六种不同的拆分方式。

再比如：4可以拆分成：4 = 4，4 = 1 + 1 + 1 + 1，4 = 2 + 2，4=1+1+2。

用f(n)表示n的不同拆分的种数，例如f(7)=6.

要求编写程序，读入n(不超过1000000)，输出f(n)%1000000000。

输入：

每组输入包括一个整数：N(1<=N<=1000000)。

输出：

对于每组数据，输出f(n)%1000000000。

样例输入：

7

样例输出：

6

一、母函数 解决

起初，一看到整数拆分，先想到的就是母函数。（思维定式害死人啊，题中 n(不超过1000000) 已经提示有大数据了，3个for循环很费时）

结果是超时！

代码如下：

#include 
       
         #include 
        
          #define MAX 1000001 int sum[MAX]; int temp[MAX]; int main(){
     int n; while(scanf("%d",&n) != EOF){
     for(int i=0; i<=n; i++){
                 sum[i] = 1;             temp[i] = 0;         } for(int i=2; i<=n; i=i<<1){
     for(int j=0; j<=n; j++){
     for(int k=0; k+j<=n; k+=i)                     temp[k+j] += sum[j];             }             memcpy(sum,temp,sizeof(int)*(n+1));             memset(temp,0,sizeof(int)*(n+1));         }         printf("%d\n",sum[n]);     } return 0; }
        
       

二、找规律，用递归解决

再网上又搜了一个递归的方法，还好没有超时。

对于奇数n=2k+1：它的拆分的第一项一定是1，考虑去掉这个1，其实就一一对应于 2k的拆分，因此f(2k+1)=f(2k). 对于偶数n=2k：考虑有1和没有1的拆分。有1的拆分，与(2k-1)的拆分一一对应，与上面奇数的情况 理由相同；没有1的拆分，将每项除以2，正好一一对应于k的所有拆分。因此f(2k)=f(2k-1)+f(k). 需要注意f(n)会很大，不要溢出了。最终结果只要求除以十亿的余数，在int的表示范围内， 因此不需要大数运算。注意余数的性质：(a+b)%m == (a%m+b%m)%m，所以只要对每个中间 结果也都取余数，就不会有溢出的问题，且不改变最终输出结果。

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