[关闭]
@zzzc18 2017-07-03T19:54:45.000000Z 字数 8151 阅读 1620

母函数(讲义)

讲课


普通型母函数:多重集组合问题

母函数是求解组合数学中计数问题的重要方法

在数学中,某个序列的母函数(又称生成函数)是一种形式幂级数,其每一项的系数可以提供关于这个序列的信息。使用母函数解决问题的方法称为母函数方法。

定义

给定数列,构造一个函数,称为该数列的母函数,其中小f函数只作为标志用,称为标志函数

标志函数有一个重要的形式就是 ,这种情况下的母函数形式为

定理 :设从 集合元素中取出 个元素的组合是 ,若限定元素 出现的次数集合为 ,则该组合数序列的母函数为:

由等比数列求和公式可知,我们称为这个母函数的闭形式,该函数具有收敛性,即在时不成立,但由于母函数不用代入 收敛性就不用考虑了


先举个例子吧

有重量为1克,3克,5克的砝码各两个,问:
1)可以称出多少种重量不同的物品》
2)若要称出质量为7克的物品,所使用的砝码有多少种本质上不同的情况?

解:
这里要用到上面的“定理 ”;
规模比较小,不妨手动模拟一下

称出物重 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
方法数 1 1 1 1 1 2 2 2 2 1 2 2 2 2 1 1 1 1 1

我们再按“定理
再将其展开,得


跟上个表格对比一下,可以恰好发现,指数与称出物重相同,而系数就等于方法数

为什么呢

实际上是即质量为 的砝码不取,取一个,和取两个
就是取了两个质量为一和一个两个质量为二的的砝码,同时,,所以质量为8的称重方法有两种,系数为二


另一个例子

有无穷多个物品时,母函数也可以写出来,见下面

hdu1028

The problem is, given an positive integer N, we define an equation like this:
 N=a[1]+a[2]+a[3]+...+a[m];
 a[i]>0,1<=m<=N;N(1<=N<=120) 
My question is how many different equations you can find for a given N.
For example, assume N is 4, we can find:
  4 = 4;
  4 = 3 + 1;
  4 = 2 + 2;
  4 = 2 + 1 + 1;
  4 = 1 + 1 + 1 + 1;
so the result is 5 when N is 4. Note that "4 = 3 + 1" and "4 = 1 + 3" is the same in this problem.

这里的母函数为


怎么回事看代码就知道了,说是 就可以了

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. #define MAXN 200
  5. using namespace std;
  6. int n;
  7. int c1[MAXN],c2[MAXN];
  8. int main(){
  9. while(scanf("%d",&n)!=EOF){
  10. int i,j,k;
  11. for(i=0;i<=n;i++){
  12. c1[i]=1;c2[i]=0;
  13. }
  14. for(i=2;i<=n;i++){//第i个式子
  15. for(j=0;j<=n;j++){//c[j]为系数
  16. for(k=0;j+k<=n;k+=i){//指数
  17. c2[j+k]+=c1[j];
  18. }
  19. }
  20. for(j=0;j<=n;j++){
  21. c1[j]=c2[j];
  22. c2[j]=0;
  23. }
  24. }
  25. printf("%d\n",c1[n]);
  26. }
  27. return 0;
  28. }

其实hdu还有几道题,都和这个类似,不说了,见附①


母函数的一些基本操作

都是有一定用处的
1.放缩:

2.加减法:

3.右移
将序列向右平移 位,并在前面补

4.求导


其操作效果就是将序列左移一位并使每一项乘以它的下标。

5.卷积规则:

的系数

对应在 中选择元素的母函数,而 对应在 中选择元素的母函数,则 对应在 选择元素的母函数。


简单序列所对应的母函数

通式:

推导手写吧


指数型母函数:多重集排列问题

定理 : 从多重集和 中选取 个元素的 -排列中,若限定元素出现的次数集合为 ,则该组合数序列的母函数为

所以指数型母函数可以长成这个样子


对于其中的表示在一个方案中某个元素出现了 次,而在不同位置中的 次出现是相同的,所以在计算排列总数时只应算作一次,所以应该除以

在应用指数母函数时应注意:展开式


应化为如下形式

真正我们需要的地方实际上是

举个例子

设有三个数字 ,两个数字 ,一个数字 ,问能组成多少个四位数?

解:指数型母函数为



故可以组成38个四位数


的Taylor展开式

求解指数型母函数时经常使用

比如说

红色病毒问题

医学界发现的新病毒因其蔓延速度和Internet上传播的"红色病毒"不相上下,被称为"红色病毒",经研究发现,该病毒及其变种的DNA的一条单链中,胞嘧啶,腺嘧啶均是成对出现的。
现在有一长度为N的字符串,满足一下条件:
(1) 字符串仅由A,T,C,G四个字母组成;
(2) A出现偶数次(也可以不出现);
(3) C出现偶数次(也可以不出现);
计算满足条件的字符串个数.
当N=2时,所有满足条件的字符串有如下6个:TT,TG,GT,GG,AA,CC.
由于这个数据肯能非常庞大,你只要给出最后两位数字即可.

Input:

    每组输入的第一行是一个整数T,表示测试实例的个数,下面是T行数据,每行一个整数N(1<=N<2^64),当T=0时结束. 

Output:

    对于每个测试实例,输出字符串个数的最后两位,每组输出后跟一个空行.

Sample Input:

    4
    1
    4
    20
    11
    3
    14
    24
    6
    0

Sample Output:

    Case 1: 2
    Case 2: 72
    Case 3: 32
    Case 4: 0

    Case 1: 56
    Case 2: 72
    Case 3: 56

Solution:

由于 只能出现偶数次,而 没有限制,所以可以构造母函数

然后快速幂求解即可,注意所求

代码见附②


指数型母函数的基本操作与普通型类似,但求导不同

上述求导也就是左移的过程

右移操作需要积分,哪位大神会可以来说说,没有也无所谓,好像今天用不上。。。

乘积也不同:
是序列的指数型母函数,是序列的指数型母函数。

那么,

的系数为


下面来一道概率题,用到指数型母函数

ST之前讲过的,不过是用dp

一个口袋中装有巧克力,巧克力的颜色有c种。先从口袋中取出一个巧克力,若取出巧克力与桌上已有的巧克力颜色相同,则将两个巧克力都取走,否则将取出的巧克力放在桌上。设从口袋中取出每种颜色的巧克力的概率相等。求取出 个巧克力后桌面上剩余 个巧克力的概率。

For each case, there are three non-negative integers: C (C <= 100), N and M (N, M <= 1000000).

dp不优化 而母函数只是展开了一个多项式,复杂度

Solution:

首先,若 则解不为 ,否则解为

所有可能的情况为
这种分发考虑到不同颜色的巧克力之间的排列关系,所以可以用指数型母函数求解

剩余 个巧克力可以转化为 种巧克力种有 种取出了奇数次, 种巧克力出现了偶数次

所以

然后展开
再把展开的多项式乘一下

注:公式太多不打了,参见国家集训队论文2009--毛文杰

代码见附③


附:

①:
1.题目UVA674
2.题目:http://acm.hdu.edu.cn/showproblem.php?pid=1398
代码:http://www.wutianqi.com/?p=590
3. 题目:http://acm.hdu.edu.cn/showproblem.php?pid=1085
代码:http://www.wutianqi.com/?p=592
4. 题目:http://acm.hdu.edu.cn/showproblem.php?pid=1171
代码:http://www.wutianqi.com/?p=594
//出自http://www.wutianqi.com/

②:

  1. #include<cstdio>
  2. #define LL long long
  3. using namespace std;
  4. LL n;
  5. LL a;
  6. int kase;
  7. LL qpow(LL x,LL k){
  8. LL ans=1;LL mul=x;
  9. LL i;
  10. for(i=1;i<=k;i<<=1){
  11. if(k&i){
  12. ans*=mul;
  13. ans%=100;
  14. }
  15. mul*=mul;
  16. mul%=100;
  17. }
  18. return ans;
  19. }
  20. int main(){
  21. while(scanf("%d",&kase)!=EOF){
  22. if(kase==0)return 0;
  23. for(int i=1;i<=kase;i++){
  24. scanf("%I64d",&n);
  25. a=qpow(4,n-1)+qpow(2,n-1);
  26. a%=100;
  27. printf("Case %d: %I64d\n",i,a);
  28. }
  29. printf("\n");
  30. }
  31. return 0;
  32. }

③:

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4. using namespace std;
  5. const int MAXN=107;
  6. const int MOD=100;
  7. int c,n,m;
  8. double tp1[MAXN],tp2[MAXN],tp1_[MAXN],tp2_[MAXN];//tp1[k]表示{[e^x-e^(-x)]/2}^m展开式中e^kx的系数,tp1_[k]表示其展开式中e^(-kx)的系数;tp2[k]、tp2_[k]同理
  9. double p[MAXN],p_[MAXN];//p[k]表示{[e^x-e^(-x)]/2}^m*{[e^x+e^(-x)]/2}^(c-m)展开式中e^kx的系数,p_[k]则表示其展开式烦人才中e^(-kx)的系数
  10. double quickPow(double a,int b) {
  11. double res=1;
  12. while(b>0) {
  13. if((b&1)==1) {
  14. res*=a;
  15. }
  16. a*=a;
  17. b>>=1;
  18. }
  19. return res;
  20. }
  21. double C(double res,int a,int b) {
  22. if(b>a-b) {
  23. b=a-b;
  24. }
  25. for(int i=1;i<=b;++i) {
  26. res*=(a-i+1.0)/i;
  27. }
  28. return res;
  29. }
  30. void getCoefficient() {//{[e^x-e^(-x)]/2}^m*{[e^x+e^(-x)]/2}^(c-m)展开式中e^kx和e^(-kx)的系数
  31. for(int k=0;k<=c;++k) {
  32. tp1[k]=tp1_[k]=tp2[k]=tp2_[k]=p[k]=p_[k]=0;
  33. }
  34. double sign,halfEm=quickPow(0.5,m);
  35. int exp;
  36. for(int i=0;i<=m;++i) {//计算前半部分表达式展开式的e^exp的系数
  37. sign=(i&1)==1?-1:1;
  38. exp=m-i-i;
  39. if(exp<0) {
  40. tp1_[-exp]+=sign*C(halfEm,m,i);
  41. }
  42. else {
  43. tp1[exp]+=sign*C(halfEm,m,i);
  44. }
  45. }
  46. halfEm=quickPow(0.5,c-m);
  47. for(int j=0;j<=c-m;++j) {//计算后半部分表达式展开式的e^exp的系数
  48. exp=c-m-j-j;
  49. if(exp<0) {
  50. tp2_[-exp]+=C(halfEm,c-m,j);
  51. }
  52. else {
  53. tp2[exp]+=C(halfEm,c-m,j);
  54. }
  55. }
  56. double fp,sp;//分别表示第一个式子和第二个式子的系数
  57. for(int i=-m;i<=m;++i) {//计算整个表达式展开式的e^exp的系数
  58. fp=i<0?tp1_[-i]:tp1[i];
  59. for(int j=-(c-m);j<=c-m;++j) {
  60. sp=j<0?tp2_[-j]:tp2[j];
  61. exp=i+j;
  62. if(exp<0) {
  63. p_[-exp]+=fp*sp;
  64. }
  65. else {
  66. p[exp]+=fp*sp;
  67. }
  68. }
  69. }
  70. }
  71. double solve() {
  72. getCoefficient();
  73. double ans=0,sign=(n&1)==1?-1:1;
  74. for(int k=1;k<=c;++k) {
  75. ans+=C(quickPow(1.0*k/c,n)*(p[k]+sign*p_[k]),c,m);
  76. }
  77. return ans;
  78. }
  79. int main() {
  80. while(scanf("%d",&c),c!=0) {
  81. scanf("%d%d",&n,&m);
  82. if(m>n||m>c||((n+m)&1)==1) {
  83. printf("0.000\n");
  84. }
  85. else if(n==0&&m==0){
  86. printf("1.000\n");
  87. }
  88. else {
  89. printf("%.3lf\n",solve());
  90. }
  91. }
  92. return 0;
  93. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注