HDU 1028 Ignatius and the Princess III——————数字拆分，母函数用法

我不是女神ヾ 2022-03-28 10:20 149阅读 0赞

# [Ignatius and the Princess III][] #

**Problem Description**  
“Well, it seems the first problem is too easy. I will let you know how foolish you are later.” feng5166 says.

“The second problem is, given an positive integer N, we define an equation like this:  
N=a\[1\]+a\[2\]+a\[3\]+…+a\[m\];  
a\[i\]>0,1<=m<=N;  
My question is how many different equations you can find for a given N.  
For example, assume N is 4, we can find:  
4 = 4;  
4 = 3 + 1;  
4 = 2 + 2;  
4 = 2 + 1 + 1;  
4 = 1 + 1 + 1 + 1;  
so the result is 5 when N is 4. Note that “4 = 3 + 1” and “4 = 1 + 3” is the same in this problem. Now, you do it!”

**Input**  
The input contains several test cases. Each test case contains a positive integer N(1<=N<=120) which is mentioned above. The input is terminated by the end of file.

**Output**  
For each test case, you have to output a line contains an integer P which indicate the different equations you have found.

**Sample Input**  
4  
10  
20

**Sample Output**  
5  
42  
627

--------------------

问题是给出一个N,可以找出多少个不同的等式  
例如，当N = 4时，我们可以找到：  
 \\qquad\\qquad\\qquad\\qquad\\qquad\\qquad\\qquad  ![在这里插入图片描述][20190110114734277.png]

#include <bits/stdc++.h>
    using namespace std;
    const int MAXN = 133;
    int C1[MAXN];//
    int C2[MAXN];//临时存放
    int n;
    int main()
    {
        
            // freopen("../in.txt","r",stdin);
            // freopen("../out.txt","w",stdout);
            while(~scanf("%d",&n))
            {
        
                    memset(C2,0,sizeof(C2));
                    for(int i=0;i<=n;++i)   C1[i] = 1;
                    for(int i=2;i<=n;++i)//从第2个多项式开始相乘
                    {
        
                            for(int j=0;j<=n;++j)// 已经得出结果的前i项
                                    for(int k=0;k+j<=n;k+=i)// k 表示下一项的指数，指数每次增加i
                                            C2[k+j] += C1[j];
                            memcpy(C1,C2,sizeof(C2));
                            memset(C2,0,sizeof(C2));
                    }
                    cout<<C1[n]<<endl;
            }
            return 0;
    }

[Ignatius and the Princess III]: http://acm.hdu.edu.cn/showproblem.php?pid=1028
[20190110114734277.png]: /images/20220328/668d8234d13a4973af1ec7d7f141c0ed.png