@zzzc18
2017-12-07T12:37:51.000000Z
字数 5926
阅读 1397
数学
母函数是求解组合数学中计数问题的重要方法
在数学中,某个序列的母函数(又称生成函数)是一种形式幂级数,其每一项的系数可以提供关于这个序列的信息。使用母函数解决问题的方法称为母函数方法。
给定数列,构造一个函数,称为该数列的母函数,其中小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的称重方法有两种,系数为二
有无穷多个物品时,母函数也可以写出来,见下面
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.
这里的母函数为
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 200
using namespace std;
int n;
int c1[MAXN],c2[MAXN];
int main(){
while(scanf("%d",&n)!=EOF){
int i,j,k;
for(i=0;i<=n;i++){
c1[i]=1;c2[i]=0;
}
for(i=2;i<=n;i++){//第i个式子
for(j=0;j<=n;j++){//c[j]为系数
for(k=0;j+k<=n;k+=i){//指数
c2[j+k]+=c1[j];
}
}
for(j=0;j<=n;j++){
c1[j]=c2[j];
c2[j]=0;
}
}
printf("%d\n",c1[n]);
}
return 0;
}
其实hdu还有几道题,都和这个类似,不说了,见附①
都是有一定用处的
1.放缩:
2.加减法:
3.右移
将序列向右平移 位,并在前面补
4.求导
5.卷积规则:
则 中 的系数
当 对应在 中选择元素的母函数,而 对应在 中选择元素的母函数,则 对应在 选择元素的母函数。
通式:
推导手写吧
定理 : 从多重集和 中选取 个元素的 -排列中,若限定元素出现的次数集合为 ,则该组合数序列的母函数为
所以指数型母函数可以长成这个样子
在应用指数母函数时应注意:展开式
设有三个数字 ,两个数字 ,一个数字 ,问能组成多少个四位数?
解:指数型母函数为
的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:
对于每个测试实例,输出字符串个数的最后两位,每组输出后跟一个空行.
由于 只能出现偶数次,而 没有限制,所以可以构造母函数
然后快速幂求解即可,注意所求
代码见附②
则
上述求导也就是左移的过程
右移操作需要积分,哪位大神会可以来说说,没有也无所谓,好像今天用不上。。。
乘积也不同:
设是序列的指数型母函数,是序列的指数型母函数。
那么,
的的系数为
ST之前讲过的,不过是用dp
一个口袋中装有巧克力,巧克力的颜色有c种。先从口袋中取出一个巧克力,若取出巧克力与桌上已有的巧克力颜色相同,则将两个巧克力都取走,否则将取出的巧克力放在桌上。设从口袋中取出每种颜色的巧克力的概率相等。求取出 个巧克力后桌面上剩余 个巧克力的概率。
For each case, there are three non-negative integers: C (C <= 100), N and M (N, M <= 1000000).
dp不优化 而母函数只是展开了一个多项式,复杂度
首先,若 则解不为 ,否则解为
所有可能的情况为
这种分发考虑到不同颜色的巧克力之间的排列关系,所以可以用指数型母函数求解
剩余 个巧克力可以转化为 种巧克力种有 种取出了奇数次, 种巧克力出现了偶数次
所以
然后展开
再把展开的多项式乘一下
①:
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