HDU/HDOJ 1521 排列组合[指数型母函数]

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

典型的指数型母函数问题,解析见:http://www.wutianqi.com/?p=2644

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
// Author: Tanky Woo
// Blog: www.WuTianQi.com
// About: HDOJ 1521 排列组合
// Link: http://acm.hdu.edu.cn/showproblem.php?pid=1521
 
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
using namespace std;
 
int n, m;
int a[15];
double c1[105], c2[105];
 
double fun(int n)
{
    double ans = 1.0;
    for(int i=1; i<=n; ++i)
        ans *= i;
    return ans;
}
 
 
int main()
{
    while(cin >> n >> m)
    {
        for(int i=0; i<n; ++i)
            cin >> a[i];
        for(int i=0; i<=n; ++i)
            c1[i] = c2[i] = 0.0;
        for(int i=0; i<=a[0]; ++i)
            c1[i] = 1.0/fun(i);
 
        for(int i=1; i<n; ++i)
        {
            for(int j=0; j<=n; ++j)
            {
                for(int k=0; k<=a[i] && k+j<=n; ++k)
                    c2[j+k] += c1[j]/fun(k);
            }
            for(int j=0; j<=n; ++j)
            {
                c1[j] = c2[j];
                c2[j] = 0;
            }
        }
        cout << fixed << setprecision(0) << c1[m]*fun(m) << endl;
 
    }
 
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《HDU/HDOJ 1521 排列组合[指数型母函数]》有17个想法

  1. 我要指出学长的错误啰~
    第38、40、 43行,其中的”<=n"应该改成"<=m"。
    因为n指的是表达式个数(这是你在母函数里面自己说的哦~呵呵),m指的是对应表达式中变量的最大指数。所以是不大于m,如果不大于n的话,有的情况就会少考虑呢。。

        1. 非常感谢学长抽时间这么耐心的回答!今天整理邮件才发现Gmail把你的回复邮件放到Spam里面去了额。。多亏了学长的解惑,大部分我都已经明白了!不过后来又去研究了一下指数型的,因为涉及到级数之类的问题,所以进展有点缓慢,以后说不定还会请教学长呢。。看你的邮件上写了no-reply,就这样回复了。总之,O(∩_∩)O谢谢学长啰!

        2. 我邮件上写了 no-reply?我应该没这么设置,方便的话麻烦截下图发我邮箱 me#tankywoo.com(#->@),,我看看是什么原因造成的,谢谢。

        3. 学长,管管你的插件额OO、

          最近每天都会发送一封卖萌邮件过来。。内容全是一样的..

发表评论

电子邮件地址不会被公开。 必填项已用*标注