hdu1521：排列组合---指数型母函数

分类: IT文章 • 2023-11-25 11:52:43

题意：

n种元素，每种有 ni个，选出 m 个的排列有多少种

题解：

指数型母函数的裸题

x^n 项的系数为 an/n!....

代码如下：

#include <iostream>
#include <stdio.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<ctype.h>
using namespace std;
#define MAXN 10000
double f[11];
double dp[2][11];
int a[11];
int main()
{
    f[0]=1;
    for(int i=1;i<=10;i++)
    {
        f[i]=f[i-1]*i;
    }
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d",a+i);
        }
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=n;j++)
            {
                for(int k=0;k<=a[i];k++)
                {
                    if(k+j>n)
                        break;
                    dp[i%2][j+k]+=dp[(i-1)%2][j]/f[k];
                }
                dp[(i-1)%2][j]=0;
            }
        }
        printf("%d
",(int)(dp[n%2][m]*f[m]+0.4));
    }
    return 0;
}

View Code

还可以用dp 做。。

dp[i][j]表示前i种元素取了j个的种类数

转移的时候乘上组合数。具体见代码：

#include <iostream>
#include <stdio.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<ctype.h>
using namespace std;
#define MAXN 10000
int dp[11][11];
int a[11];
int c[11][11];
void ini()
{
    c[0][0]=1;
    for(int i=1;i<=10;i++)
    {
        c[i][0]=1;
        for(int j=1;j<i;j++)
        {
            c[i][j]=c[i-1][j]+c[i-1][j-1];
        }
        c[i][i]=1;
    }
}
int main()
{
    int n,m;
    ini();
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d",a+i);
        }
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=m;j++)
            {
                for(int k=0;k<=a[i];k++)
                {
                    if(j+k>m)
                        break;
                    dp[i][j+k]+=dp[i-1][j]*c[j+k][k];
                }
            }
        }
        printf("%d
",dp[n][m]);
    }
    return 0;
}

View Code

hdu1521：排列组合---指数型母函数

相关推荐