HDU-1521 排列组合 (指数型母函数)

我不是女神ヾ 2022-06-09 11:20 123阅读 0赞

## 排列组合 ##

有n种物品，并且知道每种物品的数量。要求从中选出m件物品的排列数。例如有两种物品A,B，并且数量都是1，从中选2件物品，则排列有”AB”,”BA”两种。  
**Input**  
每组输入数据有两行，第一行是二个数n,m(1<=m,n<=10)，表示物品数，第二行有n个数，分别表示这n件物品的数量。  
**Output**  
对应每组数据输出排列数。(任何运算不会超出2^31的范围)  
**Sample Input**  
2 2  
1 1  
**Sample Output**  
2

思路：我在网上找了许多关于指数型母函数的博客，花了几个小时才搞明白，在这里我说一下自己的理解。首先，普通型母函数和指数型母函数最大的区别就是，普通型母函数是求组合，指数型母函数是求排列。但它们两者的代码实现差别也并不大，原理是一样的，都是手动模拟多项式相乘的过程。所以说只要照着普通型母函数的代码把指数型母函数的代码每一步的区别都搞懂，就很容易理解了。  
有一篇文章对指数型母函数解释的很详细：  
[https://wenku.baidu.com/view/c0f7ee05cc1755270722080d.html][https_wenku.baidu.com_view_c0f7ee05cc1755270722080d.html]  
文章的关键内容在下面  
![这里写图片描述][SouthEast]  
![这里写图片描述][SouthEast 1]  
![这里写图片描述][SouthEast 2]  
![这里写图片描述][SouthEast 3]  
![这里写图片描述][SouthEast 4]

#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 = 305;
    const int MOD = 30021;
    const double eps = 1e-8;
    const double PI = acos(-1.0);
    
    int Num;//因子个数 
    int v[MAXN];//v[i]表示第i个因子可以选的个数 
    int P;//P是可能的最大指数 
    double a[MAXN], b[MAXN];//a为计算结果，b为中间结果。 
    double c[MAXN];
    
    void Factorial()
    {
        c[0] = 1;
        c[1] = 1;
        for (int i = 2; i <= 20; i++)
            c[i] = c[i - 1] * i;
    }
    
    void solve()
    {
        int i, j, k;
        Factorial();
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        for (i = 0; i <= v[1]; ++i)
            a[i] = 1.0 / c[i];
        for (i = 2; i <= Num; i++)
        {
            for (j = 0; j <= P; ++j)
                for (k = 0; k + j <= P && k <= v[i]; ++k)
                    b[j + k] += a[j] / c[k];
            for (j = 0; j <= P; ++j)
            {
                a[j] = b[j];
                b[j] = 0;
            }
        }
    }
    int main()
    {
        while (scanf("%d%d",&Num,&P)!=EOF)
        {
            for (int i = 1; i <= Num; i++)
                scanf("%d", &v[i]);
            solve();
            printf("%.0lf\n", a[P] * c[P]);
        }
    }

[https_wenku.baidu.com_view_c0f7ee05cc1755270722080d.html]: https://wenku.baidu.com/view/c0f7ee05cc1755270722080d.html
[SouthEast]: /images/20220609/461890e79cbf4e18b3a4357341e980b1.png
[SouthEast 1]: /images/20220609/e27d4d13c10e46e3b1e3077b3cbf7b4a.png
[SouthEast 2]: /images/20220609/1447ee7048864d029f68d5c3e040b998.png
[SouthEast 3]: /images/20220609/1ed45809e87a42a190cf7dbc29228243.png
[SouthEast 4]: /images/20220609/cdc18bda06af4165abc4940a8393e0d3.png