ACM数论之旅16---母函数(又名生成函数)(痛并快乐着(╭ ̄3 ̄)╭)

时间:2023-03-09 02:26:26
ACM数论之旅16---母函数(又名生成函数)(痛并快乐着(╭ ̄3 ̄)╭)

(前排出售零食瓜子)

前言:

母函数是个很难的东西,难在数学

而ACM中所用的母函数只是母函数的基础

应该说除了不好理解外,其他都是非常简单的

母函数即生成函数,是组合数学中尤其是计数方面的一个重要理论和工具。

但是ACM中的母函数木有像数学那么深究,应用的都是母函数的一些基本

(就好比方程的配方,因式的分解,写起来容易,你用电脑写起来就麻烦了,所以学计算机就不要老跟数学家瞎闹( ̄3 ̄))

什么是母函数

就是把一个已知的序列和x的多项式合并起来,新产生的多项式就叫原来序列的母函数

至于怎么合并,看这个例子

序列{0,1,2,3,4,5...n}的母函数就是

f(x)=0+x+2x^2+3x^3+4x^4+...+nx^n(这个x没有任何意义,应该说,你不需要把它当做一个函数,你只要知道母函数这么写就可以了)

序列{1,1,1,1,1......}的母函数就是

f(x)=1+x+x^2+x^3+x^4....

二项式展开的序列比如这个{1,4,6,4,1,0,0,0,0,0.....}是C(4,0)到C(4,4)的系数,那它的母函数就是

f(x)=1+4x+6x^2+4x^3+1x^4

母函数就长这样,对正常人来讲,这种东西毫无意义( ° △ °|||)

那看点有意义的东西(以下都是经典题型,我从杭电ACM课件抄来的)

有1克、2克、3克、4克的砝码各一枚,能称出哪几种重量?每种重量各有几种可能方案?

假如x的幂次数表示几克的砝码

那么

1克的砝码表示为1+x^1

2克的砝码表示为1+x^2

3克的砝码表示为1+x^3

4克的砝码表示为1+x^4

每个砝码都可以选择取或不取

所以这里的1可以认为1*x^0,表示不取这颗砝码

那么把这些乘起来

(1+x^1)(1+x^2)(1+x^3)(1+x^4)

=1+(x^1)+(x^2)+2(x^3)+2(x^4)+2(x^5)+2(x^6)+2(x^7)+(x^8)+(x^9)+(x^10)

根据指数来看,我们可以称出0~10这么多的重量,其中3~7的系数为2,说明有2种称的方法

那么我们来细看一遍

0:(什么砝码都不放).......................(1种)

1:1.............................................(1种)

2:2.............................................(1种)

3:3或1+2.....................................(2种)

4:4或1+3.....................................(2种)

5:1+4或2+3.................................(2种)

6:2+4或1+2+3..............................(2种)

7:3+4或1+2+4..............................(2种)

8:1+3+4......................................(1种)

9:2+3+4......................................(1种)

10:1+2+3+4.................................(1种)

分毫不差(・ˍ・*)

所以说母函数在ACM就是这么用的,跟函数没关系,跟写法有关系。。。

再来一题

求用1分、2分、3分的邮票贴出不同数值的方案数:(每张邮票的数量是无限的)

那么

1分:(1+x^1+x^2+x^3+x^4+......)

2分:(1+x^2+x^4+x^6+x^8+......)

3分:(1+x^3+x^6+x^9+x^12+......)

然后这3个乘起来(让电脑去乘吧)

对于这种无限的,题目肯定会给你他询问的数值的范围,计算到最大的范围就可以了

附代码:

 #include<cstdio>
typedef long long LL;
const int N = + ;//假如题目只问到100为止
const int MAX = ;//题目只有1,2,3这3种邮票
LL c1[N], c2[N];//c2是临时合并的多项式,c1是最终合并的多项式
int n;
void init(){
c1[] = ;//一开始0的情况算一种
for(int i = ; i <= MAX; i ++){//把1分到MAXN的邮票合并,变成一个多项式
for(int j = ; j < N; j += i){//i分的邮票,步长是i
for(int k = ; j + k < N; k ++){//从x^0到x^N遍历一遍
c2[j + k] += c1[k];//因为j的所有项系数为1,所以c1[k]可以看成c1[k]*1;
}
}
for(int j = ; j < N; j ++){//把c2的数据抄到c1,清空c2
c1[j] = c2[j];
c2[j] = ;
}
}
}
int main(){
init();
while(scanf("%d", &n) != EOF){
printf("%I64d\n", c1[n]);
}
}

我们就来把这个模板用于实际吧

hdu 1028

http://acm.hdu.edu.cn/showproblem.php?pid=1028

题目问一个数字n能够拆成多少种数字的和

比如n=4

4 = 4;
  4 = 3 + 1;
  4 = 2 + 2;
  4 = 2 + 1 + 1;
  4 = 1 + 1 + 1 + 1;

有5种,那么答案就是5

AC代码:

 #include<cstdio>
typedef long long LL;
const int N = + ;
const int MAX = + ;
LL c1[N], c2[N];
int n;
void init(){
c1[] = ;
for(int i = ; i <= MAX; i ++){
for(int j = ; j < N; j += i){
for(int k = ; j + k < N; k ++){
c2[j + k] += c1[k];
}
}
for(int j = ; j < N; j ++){
c1[j] = c2[j];
c2[j] = ;
}
}
}
int main(){
init();
while(scanf("%d", &n) != EOF){
printf("%I64d\n", c1[n]);
}
}

再来,hdu 1398

http://acm.hdu.edu.cn/showproblem.php?pid=1398

题目说一个国家的硬币都是方形的,面值也是方形的

有1块钱,4块钱,9块钱,16块钱......一直到289块钱(17^2)

问想组成n块钱有几种方法

AC代码:

 #include<cstdio>
typedef long long LL;
const int N = + ;
const int MAX = ;
LL c1[N], c2[N];
int n;
void init(){
c1[] = ;
for(int i = ; i <= MAX; i ++){
for(int j = ; j < N; j += i*i){
for(int k = ; j + k < N; k ++){
c2[j + k] += c1[k];
}
}
for(int j = ; j < N; j ++){
c1[j] = c2[j];
c2[j] = ;
}
}
}
int main(){
init();
while(scanf("%d", &n) != EOF && n){
printf("%I64d\n", c1[n]);
}
}

都是改一些小地方,都是模板题(o゚ω゚o)

最后一道

hdu 1085

http://acm.hdu.edu.cn/showproblem.php?pid=1085

AC代码:

 #include<cstdio>
#include<cstring>
typedef long long LL;
const int N = * (++) + ;
int cost[] = {, , };
LL c1[N], c2[N];
int num[];
int MAX;
int main(){
while(~scanf("%d%d%d", &num[], &num[], &num[])){
if(num[] == && num[] == && num[] == ) break;
memset(c1, , sizeof(c1));
memset(c2, , sizeof(c2));
MAX = num[] + num[] * + num[] * ;//计算最大值
c1[] = ;
for(int i = ; i < ; i ++){
for(int j = ; j <= num[i] * cost[i]; j += cost[i]){
for(int k = ; j + k <= MAX; k ++){
c2[j + k] += c1[k];
}
}
for(int j = ; j < N; j ++){
c1[j] = c2[j];
c2[j] = ;
}
}
for(int i = ; i <= MAX + ; i ++){
if(!c1[i]){
printf("%d\n", i);
break;
}
}
}
}

母函数在数学上真的用处很大,但是我没怎么看到在ACM上有什么太大的用处(可能我做的题还不够多 T_T)

比如刚刚上面的3个例题,都有更快的做法

第一题:动态规划,时间复杂度O(n^2)

 #include<cstdio>
const int N = + ;
int dp[N];
int n;
void init(){
dp[] = ;
for(int i = ; i < N; i ++){
for(int j = i; j < N; j ++){
dp[j] += dp[j - i];
}
}
}
int main(){
init();
while(scanf("%d", &n) != EOF){
printf("%d\n", dp[n]);
}
}

第二题:动态规划,时间复杂度O(n^2)

 #include<cstdio>
const int N = + ;
int dp[N];
int n;
void init(){
dp[] = ;
for(int i = ; i <= ; i ++){
for(int j = i*i; j < N; j ++){
dp[j] += dp[j - i*i];
}
}
}
int main(){
init();
while(scanf("%d", &n) != EOF && n){
printf("%d\n", dp[n]);
}
}

第三题:≖‿≖✧特判就好了,时间复杂度O(1)

 #include<cstdio>
int a, b, c;
int ans;
int main(){
while(~scanf("%d%d%d", &a, &b, &c) && (a || b || c)){
if(a >= || a >= && b >= || a >= && b >= ) ans = a + *b + *c + ;
else if(a == ) ans = ;
else ans = a + *b + ;
printf("%d\n", ans);
}
}

哈哈哈有没有被骗的感觉,有些题目,不要陷进算法里,这题O(1)的复杂度就可以了,如果你用三个for循环,那就太慢了,而且数量不同,还没有办法预处理,如果数据量大,肯定超时

所以,母函数我们只要理解原理就好了

那么ACM的母函数讲完了(*°∀°)

之后是数学上的母函数,不想看的人就可以结束本章内容了(*°∀°)

哇哈哈╰(*°▽°*)╯我也不想讲了
自己百度去吧╰(*°▽°*)╯
据说可以求很多东西
比如Fibonacci(斐波那契)数列的通项公式
Catalan数(卡塔兰数)的通项公式也是母函数求得的
还有"牛顿二项式定理"等等。。。
想了解自己百度╰(*°▽°*)╯