首页 > 代码库 > hdu1521排列问题

hdu1521排列问题

题目链接

利用指数型母函数解决排列问题

  1.口袋中有白球2个,红球3个,黄球1个,任取3个作为一个排列,总共有多少种排列?

  类似地用指数型母函数解决

  用(1+x/1!+x2/2!)表示取白球0个,1个或者2个

  那么(1+x/1!+x2/2!)(1+x/1!+x2/2!+x3/3!)(1+x/1!)来表示所有的排列结果。

   =1+3x+4x2+19x3/6+19x4/12+6x5/12+x6/12

   =1+3*(x/1!)+8*(x2/2!)+19*(x3/3!)+38*(x4/4!)+60*(x5/5!)+60*(x6/6!)

  找到次数为3的那一项,系数为19,那么总共有19种排列。

  2.用1,2,3,4能够组成多少个5位数,要求1出现2次或者3次,2出现0次或者1次,3没有限制,4只出现偶数次。

  (x2/2!+x3/3!)(1+x)(1+x/1!+x2/2!+x3/3!+.....xk/k!+....)(1+x2/2!+x4/4!+......+x2n/(2n)!+......)

   每个式子的含义就不多解释了,读者应该能看懂它的含义。最终的结果就是x5/5!这一项的系数。

  用代码去实现母函数的计算过程很简单,它是模拟我们人工计算多项式乘积的过程,比如有多项式H1*H2*H3......

  我们先计算H1和H2的乘积,得到结果H‘,再用H‘和H3相乘......依次类推下去,直到得到最终的结果。

 

代码实现:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 using namespace std;
 7 int main()
 8 {
 9     int n,m,i,j,k;
10     double c[15],tempc[15],num[15];
11     int f[15];
12    f[0]=1;
13     for(i=1;i<=10;i++)
14     f[i]=f[i-1]*i;
15     while(~scanf("%d%d",&n,&m))
16     {
17         for(i=0;i<n;i++)
18         scanf("%lf",&num[i]);
19         memset(c,0,sizeof(c));
20         memset(tempc,0,sizeof(tempc));
21         for(i=0;i<=num[0];i++)
22         c[i]=1.0/f[i];
23         for(i=1;i<n;i++)
24         {
25             for(j=0;j<=m;j++)//所需的有意义的项数m项就足够了,多些项循环也没关系如j<=15
26             for(k=0;k<=num[i]&&k+j<=m;k++)//k+j<=m同上,但k<=num[i]要保证
27             tempc[k+j]+=(c[j]/f[k]);
28             for(j=0;j<=m;j++)
29             {
30                 c[j]=tempc[j];
31                 tempc[j]=0;
32             }
33         }
34         printf("%.0lf\n",c[m]*f[m]);//因为所求只需次数为m的项的系数
35     }
36     return 0;
37 }

 

hdu1521排列问题