Blog·Tanky WooABOUTRSS

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

27 Jun 2011
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

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

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

AC代码:

// Author: Tanky Woo
// Blog: www.WuTianQi.com
// About: HDOJ 1521 排列组合
// Link: http://acm.hdu.edu.cn/showproblem.php?pid=1521

#include 
#include 
#include 
#include 
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> 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;

    }

}