1.整数拆分为2 的幂的和
用数组a[ ]直接记录结果。
从前往后推的时候，有两种可能性，分为a[ 2m+1] 和a[ 2m ]；
易知a[ 2m+1 ]=a[ 2m ];
对于a[ 2m ]它的所有拆分方式分为两大类：
1）含有1的，这部分所有方式都去掉1，就得到a[ 2m-1 ]
2）不含有1的，也就是分出的都是2的倍数，那么都除以2，就得到a [m ]
附上AC代码：
#include<bits/stdc++.h>
using namespace std;
long long int a[1000001]={0,1,2};
long long int t,n;
int main()
{
for(int i=3;i<1000001;i++)
{
if(i%2)a[i]=a[i-1];
else a[i]=(a[i-2]+a[i/2])%1000000000;
}
cin>>t;
for(int i=0;i<t;i++)
{
cin>>n;
cout<<"case #"<<i<<":\n"<<a[n]<<endl;
}
return 0;
}
原文：https://www.cnblogs.com/MissCold/p/10703382.html