母函数
生成函数
定义
生成函数，英文是Generating Function。恕本人不才，本文只介绍生成函数的其中一种用法。
生成函数是说，构造这么一个多项式函数g(x)，使得x的n次方系数为f(n)。
对于母函数，我看到最多的是这样两句话：
-
1.“把组合问题的加法法则和幂级数的乘幂对应起来。”
-
2.“把离散数列和幂级数一 一对应起来，把离散数列间的相互结合关系对应成为幂级数间的运算关系，最后由幂级数形式来确定离散数列的构造。 “
其实这两句话我也不算太懂。先放这里，说不定以后可能会慢慢理解吧。
一个小栗子
-
还是先举个大牛博客中的例子吧：
-
有1克、2克、3克、4克砝码各一枚，问你能称出哪几种重量？每种重量各有几种方案？
下面是用母函数解决这个问题的思路：
-
首先，我们用X表示砝码，X的指数表示砝码的重量。那么，如果用函数表示每个砝码可以称的重量，
-
1个1克的砝码可以用函数X^0 + X^1表示，
-
1个2克的砝码可以用函数X^0 + X^2表示，
-
依次类推。
-
如果我们把上面2个多项式相乘，可以得到X^0 + X^1 + X^2 + X3。继续把它与X0 + X3相乘，得到X0 + X^1 + X^2 + 2*X^3 + X^4 + X^5 + X^6。
-
聪明的你，是不是发现了什么？
-
如果没有，接着把它与X0+X4相乘，最后得到X^0 + X^1 + X^2 + 2X^3 + 2X^4 + 2X^5 + 2X^6 + 2*X^7 + X^8 + X^9 + X^10。
-
由于X的指数表示的是重量，所以，在相乘时，根据幂的运算法则（同底幂相乘，指数相加），得到的结果正是所有的方案。而且，每个X前面的系数代表它有几种方案。
-
真是神奇啊。。。。
-
需要注意的是，如果有2个1克的砝码，应该用X^0 + X^1 + X2表示，而不是X0 + 2*X^1。
-
母函数还可以解决其他问题，比如，整数划分。
-
整数划分是个很经典的问题，划分规则就不再细述，直接说思路。与上面的问题相比，每种砝码的个数不再是1个，而是无限个。于是，
-
1克的砝码可以用X^0 + X^1 + X^2 + X^3 ……表示，
-
2克的砝码可以用X^0 + X^2 + X^4 + X^6……表示，
-
3克的砝码可以用X^0 + X^3 + X^6 + X^9……表示，
-
依次类推。
-
相乘后求出X^n的系数，就是结果。
-
总而言之，解决此类问题，只要模拟+好2个多项式相乘就好了。
-
大概思路是开2个数组，c1[ ]保存当前得到的多项式各项系数，c2[ ]保存每次计算时的临时结果，当每次计算完毕后，把它赋给c1，然后c2清零。
-
计算的时候，开3层for循环。最外层，记录它正在与第几个多项式相乘。第二层，表示c1中的每一项，第三层表示后面被乘多项式中的每一项。
orz大佬的博客，(上面都来自大佬写的)
原文链接：https://blog.csdn.net/dgq8211/article/details/7385718
3个糖栗子
[A 找单词]
- 来自 HDU2082
- 题面我就不复制了 ，想看点开链接看就行了。（没设密码）这两天可以来做做呦
- 题意就是尹文字符A-Z分别代表1-26，然后输入26个数分别代表多少个A-Z，然后求一共有多少种组合方式，<mark>使得和小于等于50</mark>
母函数
- 思路分析 ： 就是利用生成函数，求出x1–50的系数，模拟一下多项式相乘，不明白的话看上面的小栗子，嘻嘻。具体而言就是三层循环
第一层，循环从1-26，这26个字母当然可以吧他当成单价之类的东西，
第二层，就是0-50 也就是 要求得的指数(就是组成的数) 你可能会问为什么是50，因为题中要求 不超过50了，所以50以后的没必要在进行枚举了。
第三层，循环对应字母有几个，同时也可以优化一下，如果在枚举完字母个数之前指数已经大于50 直接进行下一层循环。
<mark>有一点特别注意一下就是初始值的问题，指数为零的初始值设为1，其他都为零，因为你要满是指数为零的系数为1 要不你的多项式相乘，不就没什么意思了吗？，当然最后，0的系数，不加进去，零不算单词</mark>
- 结合代码理解一下吧。
中间有一个
memcpy(a,b,sizeof(b));
- 其实就是一个相当复制的函数，大家应该懂，不懂得话就csdn吧。
- 还有每次把b复制给a，把b清零，是将上一个字母的结果保存到a数组里，清零是下一次进行可以前面字母没放过，直接放这个字母。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
typedef long long ll;
using namespace std;
const int maxn=1e6+1010;
#define inf 0x3f3f3f3f
const int mod=998244353;
ll n,m,t,ans;
ll a[55],b[55],num[55];
int main() {
// memcpy(a,b,sizeof(b));//将b复制到a数组
cin>>t;
while(t--){
ll sum=0;
for(int i=1;i<=26;i++)
cin>>num[i];//单词系数
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
a[0]=1;//初始值
for(int i=1;i<=26;i++)//单词
{
for(int j=0;j<=50;j++)//系数
{
for(int k=0;k<=num[i]&&j+i*k<=50;k++)//次数 就是有几个这样的单词
b[j+i*k]+=a[j];
}
memcpy(a,b,sizeof(b));//把b中已经计算过的值复制到a数组上就是他现在的系数
memset(b,0,sizeof(b));//把b数组清零开始下一个单词的计算
}
for(int i=1;i<=50;i++) sum+=a[i];
cout<<sum<<endl;;
}
return 0;
}
另一解法背包方案数
感谢涛涛大佬提供。
直接出代码吧，好理解点
其实a数组开不开无所谓，开了好理解点。
#include<stdio.h>//2019051463
#include<string.h>
int main()
{
int t,a[27],d[55],b[27],i,j,k;
for(i=1;i<=26;i++)
a[i]=i;
scanf("%d",&t);
while(t--)
{
int sum=0;
memset(d,0,sizeof(d));
d[0]=1;
for(i=1;i<=26;i++)
scanf("%d",&b[i]);
for(i=1;i<=26;i++)
{
for(j=50;j>=a[i];j--)
{
for(k=1;k<=b[i];k++)
{
if(j-k*a[i]>=0)
d[j]+=d[j-k*a[i]];
}
}
}
for(i=1;i<=50;i++)
sum+=d[i];
printf("%d\n",sum);
}
return 0;
}
[E - Ignatius and the Princess III]
来自HDU1028
同样，我就不复制题面了
- 题意分析:给出一个数，让你求出组成这个数的方式几种，(当然只有加啦)
写下题中的小栗子便于理解
4=4；
4=1+3
4=2+2
4=1+1+2；
4=1+1+1+1；
所以组成四的方式有5种
==题中还给出了输入数的范围最大是120， - 思路分析 这个题个上个题没啥大差距；就是界限改了改，因为最大是120所以直接把界限改成原本的就行了，当然害的按要求，人家的输入输出可不一样要求。只能说大体结构都一样
看代码吧，其实没有代码也行，跟上面那个题的代码一样
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
typedef long long ll;
using namespace std;
const int maxn=1e6+1010;
#define inf 0x3f3f3f3f
const int mod=998244353;
ll n,m,t,ans;
ll a[125],b[125];
int main() {
ll sum=0;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
a[0]=1;//初始值
for(int i=1;i<=120;i++)
{
for(int j=0;j<=120;j++)
{
for(int k=0;j+i*k<=120;k++)
b[j+i*k]+=a[j];
}
memcpy(a,b,sizeof(b));//把b中已经计算过的值复制到a数组上就是他现在的系数
memset(b,0,sizeof(b));//把b数组清零开始下一个单词的计算
}
while(~scanf("%lld",&n)){
cout<<a[n]<<endl;
}
return 0;
}
当然这个也可以用背包方案数。
[C - Holding Bin-Laden Captive!]
来自HDU1085
-
题意分析：就是 有1 2 5三种面值钱,输入，三个数分别表示，1,2,5的个数，求最小的不能用这些钱组成的数，
-
思路分析：这个题目明显比前两个难，就是没有给出明确的界限，然后就是不好限制他，所以这个题的难点就是找到那个限制点，剩下的就与上面相同了，首先，从1开始，他的边界一定就是1个数，2的边界就是原本那个数+22的个数，同样5也是这样，
-
所以代码就是这样子的
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
typedef long long ll;
using namespace std;
const int maxn=1e6+1010;
#define inf 0x3f3f3f3f
const int mod=998244353;
ll n,m,t,ans;
ll a[8010],b[8010],num[55],c[4]= {0,1,2,5};
int main() {
while(scanf("%lld%lld%lld",&num[1],&num[2],&num[3])&&(num[1]||num[2]||num[3])) {
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
ans=0;
a[0]=1;
for(int i=1; i<=3; i++) {
ans+=num[i]*c[i];//这个就是那个边界。下面的与前两个题都一样了
for(int j=0; j<=ans; j++) {
for(int k=0; k<=num[i]&&j+k*c[i]<=ans; k++) {
b[j+k*c[i]]+=a[j];
}
}
memcpy(a,b,sizeof(b));
memset(b,0,sizeof(b));
}
for(int i=1;;i++) if(a[i]==0) {
cout<<i<<endl;
break;
}
}
return 0;
}
指数型母函数
来自大佬-JK Chen
博客链接
常用公式
这个是扩展
京公网安备 11010502036488号