//我们需要把一个形如G(x)=(1+X^1+X^2+X^3+…)(1+X^2+X^4+X^6+…)….这样的函数 // 转换成形如F(x)=1+X+X^2 +2*X^3 +2*X^4+2*X^5+2*X^6+2*X^7+X^8+X^9+X^10 的函数/ #include #include #include using namespace std; const int max1=10001; //有两个数组 c1表示的是 c2 是中间临时数组 母函数（1+x^1+x^2+…+x^n）(1+x^2+x^4+x^6)..（根表示的是比如第一个括号中为1第二个中为2 表示的是以根为第一次增加）指数/根表示的是用 int c1[max1],c2[max1]; int main() { int n; //表示个数 while(~scanf(“%d”,&n)) { for(int i=0;i<=n;i++){ c1[i]=1; //表示的是x^i 的系数都初始化为1其实就是表示的每个x^i 都会有一种情况就是只有x^1变成 c2[i]=0; } for(int i=2;i<=n;i++)//将G(x)的第二个括号乘入F(x)中c1[i]也就是相当于便是f[x]中的x^i的系数 { for(int j=0;j<=n;j++)//表示的是fx中的对应的x^i 的系数与第二个括号里的相乘 { for(int k=0;k+j<=n;k+=i){ //因为就相当于每次都是以i为根的向上加 c2[j+k]+=c1[j];//将F(x)中第一项与G(x)中第二个括号的每一项相乘且想成之后指数就变成了k+j } } for(int j=0;j<=n;j++) { c1[j]=c2[j]; c2[j]=0; } } printf(“%d\n”,c1[n]);//表示能组成n的有多少种情况 } return 0; }
