首页 > 代码库 > 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排列问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。