生成函数入门【模板整理】

母函数

又称生成函数，是ACM竞赛中经常使用的一种解题算法，常用来解决组合方面的题目。

母函数通常解决类似如下的问题：
给5张1，4张2，3张5，要得到15，有多少种组合？
某些时候会规定至少使用3张1、1张2、0张5。
某些时候会规定有无数张1、2、5。
……

解题过程：

解题时，首先要写出表达式，通常是多项的乘积，每项由多个x^y组成。如(1+x+x^2)(1+x^4+x^8)(x^5+x^10+x^15)。
通用表达式为
(x^(v[0]n1[0])+x^(v[0](n1[0]+1))+x^(v[0]*(n1[0]+2))+…+x^(v[0]*n2[0]))
(x^(v[1]n1[1])+x^(v[1](n1[1]+1))+x^(v[1]*(n1[1]+2))+…+x^(v[1]*n2[1]))
…
(x^(v[K]n1[K])+x^(v[K](n1[K]+1))+x^(v[K]*(n1[K]+2))+…+x^(v[K]*n2[K]))

K对应具体问题中物品的种类数。

v[i]表示该乘积表达式第i个因子的权重，对应于具体问题的每个物品的价值或者权重。

n1[i]表示该乘积表达式第i个因子的起始系数，对应于具体问题中的每个物品的最少个数，即最少要取多少个。

n2[i]表示该乘积表达式第i个因子的终止系数，对应于具体问题中的每个物品的最多个数，即最多要取多少个。

对于表达式
(1+x+x^2)(x^8+x^10)(x^5+x^10+x^15+x^20)，
v[3]={1,2,5}，n1[3]={0,4,1}，n2[3]={2,5,4}。

解题的关键是要确定v、n1、n2数组的值。
通常n1都为0，但有时候不是这样。
n2有时候是无限大。

之后就实现表达式相乘，从第一个因子开始乘，直到最后一个为止。此处通常使用一个循环，循环变量为i。每次迭代的计算结果放在数组a中。计算结束后，a[i]表示权重i的组合数，对应具体问题的组合数。

循环内部是把每个因子的每个项和a中的每个项相乘，加到一个临时的数组b的对应位（这里有两层循环，加上最外层循环，总共有三层循环），之后就把b赋给a。

这些过程通常直接套用模板即可。

//为计算结果，b为中间结果。 int a[MAX],b[MAX]; //初始化a memset(a,0,sizeof(a)); a[0]=1; for (int i=1;i<=K;i++)//循环每个因子 { memset(b,0,sizeof(b)); for (int j=n1[i];j<=n2[i]&&j*v[i]<=P;j++)//循环每个因子的每一项 for (int k=0;k+j*v[i]<=P;k++)//循环a的每个项 b[k+j*v[i]]+=a[k];//把结果加到对应位 memcpy(a,b,sizeof(b));//b赋值给a }

//根据题目而定 for (i=0;i<N;i++) cin>>n1[i]>>n2[i]>>v[i]; //a数组为计算结果，b数组为中间结果 //初始化a，因为有last，所以这里无需初始化其他位  a[0]=1; int last=0; for (int i=0;i<K;i++) //循环每一个多项式 { int last2=min(last+n[i]*v[i],P);//计算下一次的last  memset(b,0,sizeof(int)*(last2+1));//只清空b[0..last2]  for (int j=n1[i];j<=n2[i]&&j*v[i]<=last2;j++) //这里是last2 ,循环因子的每一项 for (int k=0;k<=last&&k+j*v[i]<=last2;k++) //这里一个是last，一个是last2 ，循环a的每个项  b[k+j*v[i]]+=a[k]; //把结果加到对应位  memcpy(a,b,sizeof(int)*(last2+1)); //b赋值给a，只赋值0..last2  last=last2;//更新last  }

HDU1028 基本整数划分— 无限模型

问题：分解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;

每个数的数量无限，由哪些数组成也无限
我们构造生成函数为（1+x+x^2+x^3….)(1+x^2+x^4+….)…..(1+x^n) 用x来表示数,指数表示数的大小
解得x^n的系数即为所求.
dp背包做法

#include <iostream> using namespace std; int c1[130], c2[130]; int main() { int nNum; while(scanf("%d", &nNum) != EOF) { // 初始化 for(int i=0; i<=nNum; ++i) { c1[i] = 1; c2[i] = 0; } for(int i=2; i<=nNum; ++i) { for(int j=0; j<=nNum; ++j) for(int k=0; k+j<=nNum; k+=i) c2[k+j] += c1[j]; for(int j=0; j<=nNum; ++j) { c1[j] = c2[j]; c2[j] = 0; } } printf("%d\n", c1[nNum]); } return 0; }

HDU1171 HDU分家

有n种物品，价值为vi的有mi个，现在要把所有物品分成两份，要求第一份物品总价值大于等于第二份，且两份物品总价值的差最小

 //last 为所有物品总和 for (i=last/2;i>=0&&a[i]==0;i--);  cout<<last-i<<' '<<i<<endl;  //从一半开始找，找到之后先输出大的价值

HDU 1398

给你一个数让你求出1~17中每个数的平方任意组合有几种情况满足条件。

10 1 1 1 1 1 1 1 1 1 1 1 9 4 1 1 1 1 1 1 4 4 1 1 共4种分法

 for (i=1;i<=17;i++) v[i]=i*i; // 每个多项式的起始系数为0，结束系数没有因此省略，结束判断只保留乘出来的系数是否小于等于n

HDU2110

假设公司此时一共有n种价值的资产，每种价值的资产数量已知，公司资产分为3份，计算一共有多少种分割资产的方法。

for (i=0;i<N;i++) { cin>>v[i]>>n2[i]; sum+=(v[i]*n2[i]); }  //求出a[sum/3]即可

HDU2082

Input
输入首先是一个整数N，代表测试实例的个数。
然后包括N行数据，每行包括26个<=20的整数x1,x2,…..x26.

Sample Input
2
1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 2 6 2 10 2 2 5 6 1 0 2 7 0 2 2 7 5 10 6 10 2 10 6 1 9

Sample Output
7

for (i=0;i<26;i++) { cin>>n2[i]; v[i]=i+1; } 求sum（a[0]:a[50])即可

HDU2079

Input
输入数据的第一行是一个数据T，表示有T组数据。
每组数据的第一行是两个整数n(1 <= n <= 40)，k(1 <= k <= 8)。
接着有k行，每行有两个整数a(1 <= a <= 8),b(1 <= b <= 10)，表示学分为a的课有b门。

Sample Input
2
2 2
1 2
2 1
40 8
1 1
2 2
3 2
4 2
5 8
6 9
7 6
8 8

Sample Output
2
445

int last = sum(学分)； for (i=0;i<K;i++) cin>>v[i]>>n[i];  // 求a[last]即可

HDU2152

一共种了N种水果，要买由M个水果组成的水果拼盘，对于每种水果，个数上有限制，既不能少于某个特定值，也不能大于某个特定值。而且不要两份一样的拼盘。随意搭配，能组出多少种不同的方案？

for (i=0;i<N;i++) cin>>n1[i]>>n2[i]; //直接求出a[M]即可，注意数组的初始化

普通型母函数主要是来求组合的方案数，而指数型母函数是求多重排列数。

而指数型母函数主要是关于排列组合方面的问题。

分别看两个比较典型的问题对比：

普通母函数问题：有红球两个，白球、黄球各一个，试求有多少种不同的组合方案。

下面是指数型母函数的定义：

这里写图片描述

对于上面的问题“假设有8个素，其中a1重复3次，a2重复2次，a3重复3次。从中取r个组合，求其组合数。”：

这里写图片描述

HDU 1521

有n种物品，并且知道每种物品的数量。要求从中选出m件物品的排列数。例如有两种物品A,B，并且数量都是1，从中选2件物品，则排列有”AB”,”BA”两种

#include <iostream> #include <string> #include <algorithm> #include <iomanip> using namespace std; int n, m; int a[15]; double c1[105], c2[105]; double fun(int n) { double ans = 1.0; for(int i=1; i<=n; ++i) ans *= i; return ans; } int main() { while(cin >> n >> m) { for(int i=0; i<n; ++i) cin >> a[i]; for(int i=0; i<=n; ++i) c1[i] = c2[i] = 0.0; for(int i=0; i<=a[0]; ++i) c1[i] = 1.0/fun(i); for(int i=1; i<n; ++i) { for(int j=0; j<=n; ++j) { for(int k=0; k<=a[i] && k+j<=n; ++k) c2[j+k] += c1[j]/fun(k); } for(int j=0; j<=n; ++j) { c1[j] = c2[j]; c2[j] = 0; } } cout << fixed << setprecision(0) << c1[m]*fun(m) << endl; } }

以上这些题目解法都是最暴力的，这样在数据范围小的时候可以接受，这些题目大多来源于杭电等学校的期末考试题，但是生成函数的用途远不止如此；

下面介绍一下优化算法

优化：

一.数学积分，多项式展开式（常用）
生成函数解决问题如果暴力计算的话，优势并不是特别明显，
一般都是利用数学积分成一个式子，然后把所有式子都乘起来
然后再利用展开式展开得到某一项的结果，所以在最后的答案代码中
往往看不到生成函数的痕迹。

我们来看一个例子（ HDU6239）
求这里写图片描述

在这里要求这个和有3种方法，
（1），数两次原理：
首先有这样一个结论对于一个数列第i项是C(i+k-1,k)
其前缀和就是C(i+k,k+1)
此时求和的两个数列分别是
（1）n，……5,4,3,2,1
( 2 ) i(i+1)/2 即C（i+1，2）
（1） 5 4 3 2 1
（2） 1 3 6 10 15 21 28 36
对于这样两个数列求卷积，就等于把第二个数列求两次前缀和
即C(n,2) 求两次前缀和就是C(n+2,4)

（2）. 利用生成函数
这里写图片描述

所以最后得到的和就是C(n+2,4)

那么如何利用生成函数呢？ 对于上面这个式子 要计算两个数列的卷积 a 5 4 3 2 1 b 1 3 6 10 15 21 28 36 对于第一个数列求和 x/（1-x）^2 对于第二个数列求和 x/ (1-x)^3 乘起来是 (x^2)/(1-x)^5 （6） 由下图（7）式 对于这个式子展开第k项正好是C（k,k+4） 但是由于（7）式是不带分子上的X^2的 所以相当于整体乘了一个x^2 这样在找（6）式中x次数为n的项的时候只需要在（7)式中向前找两项即找x次数是n-2的即可 第k-2项是C（k-2,k+2）即C(4,k+2) 所以第n-2项就是C（4，n+2） 就是a，b两个数列的卷积结果了

（3）: 拉格朗日插值法|牛顿插值法：
对于分母分子求出前四项分别进行插值

那么什么是拉格朗日插值法呢？？？

最早来源

这里写图片描述

例题：NYOJ 178
描述
大家一定见过这种题目：给你一些数请找出这些数之间的规律，写出下一个满足该规律的数。
比如：2 5 10 17 26，则可以看出这些数符合n*n+1这个通项公式，则下一个数为37。
这种通项公式不只一个，所以答案是不唯一的。但如果已知了N个数，且已知其通项公式是一个次数小于N的多项式，则答案就唯一确定了。
现在给你一个数列，请找出规律并求出其下一个数为多少？
输入
第一行是一个整数T表示测试数据的组数(T<=20)
每组测试数据的第一行是一个整数N（1<=N<=5)
随后的一行有N个整数,表示该数列已知了的N个整数(这N个整数的值都不大于1000)。
输出
输出符合规律的下一个数
样例输入
2
2
1 2
5
2 5 10 17 26
样例输出
3
37

思路：Lagrange插值公式的运用.,
一种离散数学上的方法：
Lagrange插值法和Newton插值法解决实际问题中关于只提供复杂的离散数据的函数求值问题，
通过将所考察的函数简单化，构造关于离散数据实际函数f（x）的近似函数P（x），从而可以计算未知点出的函数值，是插值法的基本思路。

#include <math.h>  #include <queue>  #include <deque>  #include <vector>  #include <stack>  #include <stdio.h>  #include <ctype.h>  #include <string.h>  #include <stdlib.h>  #include <iostream>  #include <algorithm>  using namespace std; #define Max(a,b) a>b?a:b  #define Min(a,b) a>b?b:a  #define mem(a,b) memset(a,b,sizeof(a))  int dir[4][2]= { 
  { 
  1,0},{-1,0},{ 
  0,1},{ 
  0,-1}}; const double eps = 1e-6; const double Pi = acos(-1.0); static const int inf= ~0U>>2; static const int maxn =110; int in[100],out[100],Map[200]; int T,i,j,n; double lagrange(double x,int n) //函数定义  { double xy[5][5]; for(int i=0; i<n; i++) //录入插值点  { xy[i][0]=i+1; cin>>xy[i][1]; } double lag=0.0; for(int i=0; i<n; i++) { double ji=1.0; for(int j=0; j<n; j++) { if(i!=j) ji=ji*((x-xy[j][0])/(xy[i][0]-xy[j][0])); //基函数  } lag=lag +ji* xy[i][1]; //函数值  } return lag; } int main() { cin>>T; while(T--) { cin>>n; cout<<lagrange(n+1,n)<<endl; } return 0; }

标准模板：

#include <cmath>  using namespace std; double PointsInsert(int n,double xi,double *x,double *y) { //n为插值点的个数  //N=2为两点高斯插值，即线性插值  //N=3为三点高斯插值，即二次插值  //xi为目标点的坐标，x和y为插值点的坐标值和数值  int i,j; double *L; double up,low,result; L=new double[n+1]; for (i=1;i<=n;i++) { up=1.0;low=1.0; for (j=1;j<=n;j++) { if (j!=i) { up=up*(xi-x[j]); low=low*(x[i]-x[j]); } } L[i]=up/low; } result=0.0; for (i=1;i<=n;i++) { result=result+L[i]*y[i]; } delete[] L; return result; } int main() { int n,i; double *x,*y,xi; n=2; while (n>1) { cout<<"请输入插值点的个数(-1结束运算):"; cin>>n; if (n>1) { cout<<"您要求"<<n<<"点插值计算!"<<endl; x=new double[n+1]; y=new double[n+1]; cout<<"请输入"<<n<<"个点的x,y值:"<<endl; for (i=1;i<=n;i++) { cin>>x[i]>>y[i]; } cout<<"请输入需要插值的点的x:"; cin>>xi; cout<<"插值计算结果为:"<<PointsInsert(n,xi,x,y)<<endl; cout<<"插值计算完成！"<<endl; cout<<""<<endl; delete[] x; delete[] y; } } return 0; }

二 .bitset

C++ bitset——高端压位卡常题必备STL

bitset存储二进制数位。
可以理解成 vector< bool >
bitset就像一个bool类型的数组一样，但是有空间优化——bitset中的一个素一般只占1 bit，相当于一个char素所占空间的八分之一。

bitset中的每个素都能单独被访问，例如对于一个叫做foo的bitset，表达式foo[3]访问了它的第4个素，就像数组一样。

bitset有一个特性：整数类型和布尔数组都能转化成bitset。

bitset的大小在编译时就需要确定。如果你想要不确定长度的bitset，请使用（奇葩的）vector。

定义一个bitset
// constructing bitsets
include // std::cout
include // std::string
include // std::bitset

int main ()
{
std::bitset<16> foo;
std::bitset<16> bar (0xfa2);
std::bitset<16> baz (std::string(“0”));

std::cout << “foo: ” << foo << ‘\n’;
std::cout << “bar: ” << bar << ‘\n’;
std::cout << “baz: ” << baz << ‘\n’;

return 0;
}
输出结果：

foo: 0000000000000000
bar: 00000
baz: 0000000
bitset的运算
bitset的运算就像一个普通的整数一样，可以进行与(&)、或(|)、异或(^)、左移(<<)、右移(>>)等操作。

// bitset operators #include <iostream> // std::cout #include <string> // std::string #include <bitset> // std::bitset int main () { std::bitset<4> foo (std::string("1001")); std::bitset<4> bar (std::string("0011")); std::cout << (foo^=bar) << '\n'; // 1010 (XOR,assign) std::cout << (foo&=bar) << '\n'; // 0010 (AND,assign) std::cout << (foo|=bar) << '\n'; // 0011 (OR,assign) std::cout << (foo<<=2) << '\n'; // 1100 (SHL,assign) std::cout << (foo>>=1) << '\n'; // 0110 (SHR,assign) std::cout << (~bar) << '\n'; // 1100 (NOT) std::cout << (bar<<1) << '\n'; // 0110 (SHL) std::cout << (bar>>1) << '\n'; // 0001 (SHR) std::cout << (foo==bar) << '\n'; // false (0110==0011) std::cout << (foo!=bar) << '\n'; // true (0110!=0011) std::cout << (foo&bar) << '\n'; // 0010 std::cout << (foo|bar) << '\n'; // 0111 std::cout << (foo^bar) << '\n'; // 0101 return 0; } 上面代码的输出结果见注释。（注意，这段代码涉及赋值操作） bitset的相关函数 对于一个叫做foo的bitset： foo.size() 返回大小（位数） foo.count() 返回1的个数 foo.any() 返回是否有1 foo.none() 返回是否没有1 foo.set() 全都变成1 foo.set(p) 将第p + 1位变成1 foo.set(p, x) 将第p + 1位变成x foo.reset() 全都变成0 foo.reset(p) 将第p + 1位变成0 foo.flip() 全都取反 foo.flip(p) 将第p + 1位取反 foo.to_ulong() 返回它转换为unsigned long的结果，如果超出范围则报错 foo.to_ullong() 返回它转换为unsigned long long的结果，如果超出范围则报错 foo.to_string() 返回它转换为string的结果

HDU 1085

给出若干枚12和5硬币，求问最小的无法组成的面值

构造生成函数：
这里写图片描述

int last = num[1]*1+num[2]*2+num[3]*5; for (i=0;i<=last;i++) if (a[i]==0) break; cout<<i<<endl;

code:(bitset优化)

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<bitset> //by NeighThorn using namespace std; const int maxn=1000+5; bitset<8005> s; int a,b,c,ans; signed main(void){ while(scanf("%d%d%d",&a,&b,&c)){ if(a==0&&b==0&&c==0) break; s.reset(); for(int i=0;i<=a;i++) for(int j=0;j<=b;j++) s.set(i+j*2); for(int i=a+b*2;i>=0;i--) if(s[i]) for(int j=c;j>=0;j--) s.set(i+j*5); int ans=1; while(s[ans]) ans++; printf("%d\n",ans); } return 0; }

例题：

[UVALive-6886]
打高尔夫，一球能打n种距离，有m个洞，给出每个洞的位置，问两杆之内，在只能往前打的情况下，能进的有几种洞
Sample Input
3
1
3
5

6
2
4
5
7
8
9
Sample Output
4

#include <iostream> #include<cstdio> #include<vector> #include<algorithm> #include<cstring> #include<bitset> using namespace std; bitset<>x,y; int n,m; int a[]; int main() { while(cin>>n) { x.reset(); y.reset(); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); x[a[i]] = 1; } y=x; for(int i=1;i<=n;i++) { y|=x<<a[i];//x左移a[i]代表整个集合的所有素都+a[i] //cout<<(x<<a[i])<<" "; } int num; scanf("%d",&m); int xx= 0; for(int i=1;i<=m;i++) { scanf("%d",&num); xx+=y[num]; } printf("%d\n",xx); } return 0; }

三 .FFT 快速傅里叶变换

API：给定两个数组a,b, 进行快速多项式计算（乘法，异或等）
结果保存在a【0】里
具体步骤：
1 补0得到两个2n次多项式
2 计算DFTa DFTb（离散傅里叶变换）
3两个数组的每一项对应相乘
4 计算IDFT得到 a[0]
FWT（异或运算），NTT(快速数论变换)

这里写图片描述

例题：bzoj3771

参考博客列表：
1.网上流传的最有名的两个博客
博客1
博客2
以上讲解部分转自博客2
2
参考课件
3
集训队论文
4.
拉格朗日插值法视频
5 HDU6239

今天的文章生成函数入门【模板整理】分享到此就结束了，感谢您的阅读。

生成函数入门【模板整理】

母函数

优化：

例题：bzoj3771

相关推荐