- 题目描述：
-
一个整数总可以拆分为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 <stdio.h>
#include <string.h>
#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 <stdio.h>
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;
}