@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的称重方法有两种,系数为二
有无穷多个物品时,母函数也可以写出来,见下面
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:
对于每个测试实例,输出字符串个数的最后两位,每组输出后跟一个空行.
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
由于 只能出现偶数次,而 没有限制,所以可以构造母函数
然后快速幂求解即可,注意所求
代码见附②
则
上述求导也就是左移的过程
右移操作需要积分,哪位大神会可以来说说,没有也无所谓,好像今天用不上。。。
乘积也不同:
设是序列的指数型母函数,是序列的指数型母函数。
那么,
的的系数为
ST之前讲过的,不过是用dp
一个口袋中装有巧克力,巧克力的颜色有c种。先从口袋中取出一个巧克力,若取出巧克力与桌上已有的巧克力颜色相同,则将两个巧克力都取走,否则将取出的巧克力放在桌上。设从口袋中取出每种颜色的巧克力的概率相等。求取出 个巧克力后桌面上剩余 个巧克力的概率。
For each case, there are three non-negative integers: C (C <= 100), N and M (N, M <= 1000000).
dp不优化 而母函数只是展开了一个多项式,复杂度
首先,若 则解不为 ,否则解为
所有可能的情况为
这种分发考虑到不同颜色的巧克力之间的排列关系,所以可以用指数型母函数求解
剩余 个巧克力可以转化为 种巧克力种有 种取出了奇数次, 种巧克力出现了偶数次
所以
然后展开
再把展开的多项式乘一下
注:公式太多不打了,参见国家集训队论文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/
②:
#include<cstdio>
#define LL long long
using namespace std;
LL n;
LL a;
int kase;
LL qpow(LL x,LL k){
LL ans=1;LL mul=x;
LL i;
for(i=1;i<=k;i<<=1){
if(k&i){
ans*=mul;
ans%=100;
}
mul*=mul;
mul%=100;
}
return ans;
}
int main(){
while(scanf("%d",&kase)!=EOF){
if(kase==0)return 0;
for(int i=1;i<=kase;i++){
scanf("%I64d",&n);
a=qpow(4,n-1)+qpow(2,n-1);
a%=100;
printf("Case %d: %I64d\n",i,a);
}
printf("\n");
}
return 0;
}
③:
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=107;
const int MOD=100;
int c,n,m;
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]同理
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)的系数
double quickPow(double a,int b) {
double res=1;
while(b>0) {
if((b&1)==1) {
res*=a;
}
a*=a;
b>>=1;
}
return res;
}
double C(double res,int a,int b) {
if(b>a-b) {
b=a-b;
}
for(int i=1;i<=b;++i) {
res*=(a-i+1.0)/i;
}
return res;
}
void getCoefficient() {//{[e^x-e^(-x)]/2}^m*{[e^x+e^(-x)]/2}^(c-m)展开式中e^kx和e^(-kx)的系数
for(int k=0;k<=c;++k) {
tp1[k]=tp1_[k]=tp2[k]=tp2_[k]=p[k]=p_[k]=0;
}
double sign,halfEm=quickPow(0.5,m);
int exp;
for(int i=0;i<=m;++i) {//计算前半部分表达式展开式的e^exp的系数
sign=(i&1)==1?-1:1;
exp=m-i-i;
if(exp<0) {
tp1_[-exp]+=sign*C(halfEm,m,i);
}
else {
tp1[exp]+=sign*C(halfEm,m,i);
}
}
halfEm=quickPow(0.5,c-m);
for(int j=0;j<=c-m;++j) {//计算后半部分表达式展开式的e^exp的系数
exp=c-m-j-j;
if(exp<0) {
tp2_[-exp]+=C(halfEm,c-m,j);
}
else {
tp2[exp]+=C(halfEm,c-m,j);
}
}
double fp,sp;//分别表示第一个式子和第二个式子的系数
for(int i=-m;i<=m;++i) {//计算整个表达式展开式的e^exp的系数
fp=i<0?tp1_[-i]:tp1[i];
for(int j=-(c-m);j<=c-m;++j) {
sp=j<0?tp2_[-j]:tp2[j];
exp=i+j;
if(exp<0) {
p_[-exp]+=fp*sp;
}
else {
p[exp]+=fp*sp;
}
}
}
}
double solve() {
getCoefficient();
double ans=0,sign=(n&1)==1?-1:1;
for(int k=1;k<=c;++k) {
ans+=C(quickPow(1.0*k/c,n)*(p[k]+sign*p_[k]),c,m);
}
return ans;
}
int main() {
while(scanf("%d",&c),c!=0) {
scanf("%d%d",&n,&m);
if(m>n||m>c||((n+m)&1)==1) {
printf("0.000\n");
}
else if(n==0&&m==0){
printf("1.000\n");
}
else {
printf("%.3lf\n",solve());
}
}
return 0;
}