首页 > 代码库 > 组合数学 - 母函数 --- 模板 + 详解
组合数学 - 母函数 --- 模板 + 详解
Square Coins
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 8341 Accepted Submission(s): 5674
There are four combinations of coins to pay ten credits:
ten 1-credit coins,
one 4-credit coin and six 1-credit coins,
two 4-credit coins and two 1-credit coins, and
one 9-credit coin and one 1-credit coin.
Your mission is to count the number of ways to pay a given amount using coins of Silverland.
Mean:
略
analyse:
母函数的模板题。后面会讲有关母函数的介绍。
Time complexity:O(n^3)
Source code:
// Memory Time// 1347K 0MS// by : Snarl_jsb// 2014-09-18-10.23#include<algorithm>#include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>#include<vector>#include<queue>#include<stack>#include<map>#include<string>#include<climits>#include<cmath>#define N 305#define LL long longusing namespace std;vector<int> val;vector<int>c1(N),c2(N);void make_square(){ for(int i=1;i<=18;++i) val.push_back(i*i);}int main(){ ios_base::sync_with_stdio(false); cin.tie(0);// freopen("C:\\Users\\ASUS\\Desktop\\cin.cpp","r",stdin);// freopen("C:\\Users\\ASUS\\Desktop\\cout.cpp","w",stdout); make_square(); int n; while(cin>>n,n) { for(vector<int>::iterator iter=c1.begin();iter!=c1.end();++iter) *iter=1; c2.clear(); for(int i=2;i<=17;++i) { for(int j=0;j<=n;++j) { for(int k=0;k+j<=n;k+=val[i-1]) { c2[j+k]+=c1[j]; } } for(int j=0;j<=n;++j) { c1[j]=c2[j]; c2[j]=0; } } cout<<c1[n]<<endl; } return 0;}
母函数(Generating Function)
No1.What is the Generating Function?
我只说我的理解,其他的官方定义自行百度。
首先,母函数是一个序列的表达式,由他可以表达一个有规律的序列,我们通过它可以求得这个序列,从而解决一些问题。
母函数,顾名思义,就是母亲,那就说明,在这个函数里面还有儿子,即子函数。说白了,就是子函数可以看作是母函数的一个子集。
而如何把这些子函数用一个母函数来表示呢?即所谓的通项公式,我个人觉的这是问题的症结之处,解决了这一症结,那么,后面的问题就容易多了。
为什么母函数具有这样的功能呢?
从这两句话中你可能有一些启发:
"把组合问题的加法法则和幂级数的t的乘幂的相加对应起来"
"母函数的思想很简单—就是把离散数列和幂级数一一对应起来,把离散数列间的相互结合关系对应成为幂级数间的运算关系,最后由幂级数形式来确定离散数列的构造. "
No2.What type of problem for Generating Function?
母函数有普通型的,也有指数型的,当然,在ACM中指数型的至今还未碰到,所以这里只讲一下普通型的。
我们知道,母函数在组合数学中运用得非常广泛,主要是用来求解可重集的组合数。
母函数最近经典的运用莫过于整数拆分,即:对于给定的一个数n,问n的拆分有多少种情况?
又如:有n种物品,其中第i种物品有a1个,第二种有a2个,第三种有a3个....而且第1个物品的价值为v1,第二个的为v2....现在问你从中选择若干件物品出来,使得这些物品的价值之和为m,共有多少种选择方式?
这就是母函数的原形,母函数就是求解这类问题的。
No3.How to Structure a Generating Function for a problem?
构造一个序列的母函数,这个要看具体问题,并没有真正通用的模板,但是母函数的构造有很多相同之处。
下面用一个例子来说明:
有1克、2克、3克、4克的砝码各一 枚,能称出哪几种重量?每种重量各有几种可能方案?
考虑用母函数来接吻这个问题:
我们假设x表示砝码,x的指数表示砝码的重量,这样:
1个1克的砝码可以用函数1+x表示,
1个2克的砝码可以用函数1+x2表示,两个2克的砝码可以用函数1+x4表示,
1个3克的砝码可以用函数1+x3表示,两个三克的可以用函数1+x6表示,...
1个4克的砝码可以用函数1+x4表示,....
我们拿1+x2来说,前面已经说过,x表示砝码,x的指数表示重量,即这里就是一个质量为2的砝码,那么前面的1表示什么?1代表重量为2的砝码数量为0个。
1+x2表示了两种情况:1表示质量为2的砝码取0个的情况,x2表示质量为2的砝码取1个的情况。
这里说下各项系数的意义:
在x前面的系数a表示相应质量的砝码取a个,而1就表示相应砝码取0个,这里可不能简单的认为相应砝码取0个就该是0*x2
几种砝码的组合可以称重的情况,可以用以上几个函数的乘积表示:
(1+x)(1+x2)(1+x3)(1+x4)
=(1+x+x2+x3)(1+x3+x4+x7)
=1+x+x2+2x3+2x4+2x5+2x6+2x7+x8+x9+x10
从上面的函数知道:可称出从1克到10克,系数便是方案数
例如右端有2x5 项,即称出5克的方案有2:5=3+2=4+1;同样,6=1+2+3=4+2;10=1+2+3+4。
故称出6克的方案有2,称出10克的方案有1 。
No4.How to solve polynomial expanasion?
可以说整个母函数求解过程中,多项式的展开是一个难点,也是解题的关键。
多项式展开:
我们用两个数组c1[],c2[]来求解,c1[i]=b表示: xi 前面的系数为b,即表示bxi 的系数b;
而c2[]数组只起到中间存值的作用,它是用来维护c1迭代的不变性的。
步骤:
1)根据第一个表达式(第一个括号)给c1赋初值;
2)从第二个表达式开始,依次与c1合并,并将中间结果保存到c2[],然后将c2复制给c1,c2清零。
3)重复第二步,直到所有的表达式都合并完成。
4)统计得出答案(具体看题目要求)。
模板代码:
////第1种物品的价值为1,有无限个;//第2种物品的价值为2,有无限个;//第3种物品的价值为3,有无限个;//.......//问取出一些物品的价值总和为n的取法有多少个?#include <iostream>using namespace std;const int _max = 10001;int c1[_max], c2[_max];// c1是保存各项质量砝码可以组合的数目// c2是中间量,保存每一次的情况,维持c1的不变性int main(){ int nNum; int i, j, k; while(cin >> nNum) //要组合的目标数 { for(i=0; i<=nNum; ++i) // ---- ① 首先对c1初始化,由第一个表达式(1+x+x2+..xn)初始化,把质量从0到n的所有砝码都初始化为1. { c1[i] = 1; c2[i] = 0; } for(i=2; i<=nNum; ++i) // ----- ②i从2到n遍历,这里i就是指第i个表达式,上面给出的第二种母函数关系式里,每一个括号括起来的就是一个表达式。 { for(j=0; j<=nNum; ++j) // -----③j 从0到n遍历,这里j就是只一个表达式里第j个变量,比如在第二个表达式里:(1+x2+x4....)里,第j个就是x2*j. for(k=0; k+j<=nNum; k+=i) // ---- ④ k表示的是第j个指数,所以k每次增i(因为第i个表达式的增量是i)。 { c2[j+k] += c1[j]; } for(j=0; j<=nNum; ++j) // ---- ⑤把c2的值赋给c1,而把c2初始化为0,因为c2每次是从一个表达式中开始的 { c1[j] = c2[j]; c2[j] = 0; } } cout << c1[nNum] << endl; } return 0;}
组合数学 - 母函数 --- 模板 + 详解