HDU-1028 Ignatius and the Princess III(母函数)

落日映苍穹つ 2022-06-09 10:48 145阅读 0赞

## Ignatius and the Princess III ##

“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可以拆分成多少种数的和的组合，比如N=4的时候，4=4，4=3+1，4=2+2，4=2+1+1，4=1+1+1+1。所以输出5。

思路：这是一道母函数入门题，题目要求一个数N能拆分成多少种数的和，因为N<=120，所以能用来组合的数只有1到120，1可以有120/1=120个，2可以有120/2=60个，依次类推，我们就把这题变成了一道已知有许多个数，每个数都可以用指定次数，问组合成N的方法有多少种。然后套母函数的模板即可。  
模板：[http://blog.csdn.net/kele52he/article/details/77834848][http_blog.csdn.net_kele52he_article_details_77834848]

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <cstdlib>
    #include <cmath>
    #include <vector>
    #include <queue>
    #include <map>
    #include <algorithm>
    #include <set>
    #include <functional>
    using namespace std;
    typedef long long LL;
    typedef unsigned long long ULL;
    const int INF = 1e9 + 5;
    const int MAXN = 1007;
    const int MOD = 30021;
    const double eps = 1e-8;
    const double PI = acos(-1.0);
    
    int Num;//因子个数
    int n1[MAXN];//n1[i]表示该乘积表达式第i个因子的起始系数
    int n2[MAXN];//n2[i]表示该乘积表达式第i个因子的终止系数
    int v[MAXN];//v[i]表示该乘积表达式第i个因子的权重
    int P;//P是可能的最大指数
    int a[MAXN], b[MAXN];//a为计算结果，b为中间结果。 
    
    void solve()
    {
        memset(a, 0, sizeof(a));
        a[0] = 1;
        for (int i = 1; i <= Num; i++)//循环每个因子 
        {
            memset(b, 0, sizeof(b));
            for (int j = n1[i]; j <= n2[i] && j*v[i] <= P; j++)//循环每个因子的每一项 
                for (int k = 0; k + j*v[i] <= P; k++)//循环a的每个项 
                    b[k + j*v[i]] += a[k];//把结果加到对应位 
            memcpy(a, b, sizeof(b));//b赋值给a 
        }
    }
    
    int main()
    {
        int x;
        int k = 0;
        Num = 120;
        P = 120;
        for (int i = 1; i <= Num; i++)
        {
            n1[i] = 0;
            n2[i] = 120 / i;
            v[i] = i;
        }
        solve();
        while (scanf("%d", &x) != EOF)
            printf("%d\n", a[x]);
    }

[http_blog.csdn.net_kele52he_article_details_77834848]: http://blog.csdn.net/kele52he/article/details/77834848