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