[关闭]
@zzzc18 2017-12-07T04:37:51.000000Z 字数 5926 阅读 632

母函数

数学


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

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

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


定义

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

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


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


先举个例子吧

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


解:

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

称出物重 0 1 2 3 4 5 6 7 8 9
方法数 1 1 1 1 1 2 2 2 2 1

称出物重 10 11 12 13 14 15 16 17 18
方法数 2 2 2 2 1 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. }

  1. for(i=2;i<=n;i++){//第i个式子
  2. for(j=0;j<=n;j++){//c[j]为系数
  3. for(k=0;j+k<=n;k+=i){//指数
  4. c2[j+k]+=c1[j];
  5. }
  6. }
  7. for(j=0;j<=n;j++){
  8. c1[j]=c2[j];
  9. c2[j]=0;
  10. }
  11. }
  12. printf("%d\n",c1[n]);
  13. }
  14. return 0;
  15. }

其实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:

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


Solution:

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


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

代码见附②


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

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

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


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

那么,


的系数为


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

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

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

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

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


Solution:

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

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

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

所以

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


①:

1.题目UVA674
2.题目:http://acm.hdu.edu.cn/showproblem.php?pid=1398

代码:http://www.wutianqi.com/?p=590

1. 题目:http://acm.hdu.edu.cn/showproblem.php?pid=1085
   代码:http://www.wutianqi.com/?p=592
2. 题目:http://acm.hdu.edu.cn/showproblem.php?pid=1171
  代码:http://www.wutianqi.com/?p=594
   //出自http://www.wutianqi.com/?p=596
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注