HDOJ-1028 Ignatius and the Princess III

题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1028

题目大意

数字拆分模板题，对于每一个$N$，输出拆分方式数量。例如对于4存在五种拆分方式：

4 = 4;
4 = 3 + 1;
4 = 2 + 2;
4 = 2 + 1 + 1;
4 = 1 + 1 + 1 + 1;

Input

输入由多个测试用例组成。 每行包含一个整数$N$，满足 $(1≤N≤120)$。

Sample Input

4
10
20

Sample Output

5
42
627

Solution

构造母函数：$G(x) = (1 + x + x^2 + ...)(1 + x^2 + x^4 + ...)(1 + x^3 + x^6 + ...)...$

然后让计算机每次相乘前两项，在c2数组中计算，再存储到c1数组，$i$表示当前正在计算第$1$个多项式和第$i$个多项式相乘。

#include <bits/stdc++.h>
using namespace std;
int c1[125],c2[125];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    for(int i=0;i<=120;i++){
        c1[i]=1;
    }
    for(int i=2;i<=120;i++){
        for(int j=0;j<=120;j++){
            for(int k=0;k+j<=120;k+=i){
                c2[k+j]+=c1[j];
            }
        }
        for(int j=0;j<=120;j++){
            c1[j]=c2[j];
            c2[j]=0;
        }
    }
    int n;
    while (cin>>n) cout<<c1[n]<<'\n';
}