母函数通用模板
1.问题描述2.写程序用的目函数模板：3 例子4 参考文献
1.问题描述
母函数是组合数学中用来计数的一种方法，便于大家写程序来解决一些问题；
生成函数即母函数，是组合数学中尤其是计数方面的一个重要理论和工具。 生成函数有普通型生成函数和指数型生成函数两种，其中普通型用的比较多。 形式上说，普通型生成函数用于解决多重集的组合问题， 而指数型母函数用于解决多重集的排列问题。 母函数还可以解决递归数列的通项问题（例如使用母函数解决斐波那契数列的通项公式）
最早提出母函数的人是法国数学家LaplaceP.S.在其1812年出版的《概率的分析理论》中明确提出“生成函数的计算”，书中对生成函数思想奠基人——Euler L在18世纪对自然数的分解与合成的研究做了延伸与发展。生成函数的理论由此基本建立。
2.写程序用的目函数模板：
这个母函数目标可以套用，理解不了先可以套用，具体看第3部分，套用后就AC了；
#include<iostream>
using namespace std;
//动态内存分配不用memset或memcpy来初始化或复制数组
int main()
{
int i,j,m;//循环变量
int k;//有k种硬币，则有k个()相乘
int *v = new int[k+1];//v[0]不用,v[i]为第i种硬币的价值
//s和e的含义:第i种硬币至少用s[i]个,至多用e[i]个
int *s = new int[k+1];//s[0]不用
int *e = new int[k+1];//e[0]不用
/*
* k，v，s，e的具体值需要自行输入或设置
*/
//计算最高次数MAX = 最高次数
int MAX = 0;
for(i=1;i<=k;i++)
MAX += v[i]*e[i];
int *a = new int[MAX+1];//a和b用于记录运行结果
int *b = new int[MAX+1];
for(i=0;i<=MAX;i++)
{
a[i] = 0;
b[i] = 0;
}
a[0] = 1;
//下面是相乘的过程，代码很难理解!!!
for(i=1;i<=k;i++)
{
//for(m=0;m<=MAX;m++) b[m]=0;
for(j=s[i];j<=e[i] && j*v[i]<=MAX;j++)
for(m=0;m+j*v[i]<=MAX;m++)
b[m+j*v[i]] += a[m];
for(m=0;m<=MAX;m++)
{
a[m] = b[m];
b[m] = 0;
}
}
/*
*程序运行至此，a[1],a[2],...,a[MAX]是x,x^2,...,x^MAX的系数
*/
return 0;
}
3 例子
代码如下：
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<memory>
#include<string>
#include<stdexcept>
#include<vector>
#include<list>
#include<map>
#include<algorithm>
#include<functional>
using namespace std;
/*小Z有n枚硬币，面值分别为w1,w2,⋯,wn。请问他总共有多少种办法凑出v块钱？
请注意，相同面值的硬币我们也认为是不同的。*/
//方法：利用母函数，使用母函数模板来实现这个功能
//定义使用的全局变量
vector<int> arr;
const int N = 900;
int ans(int n,int v)
{
/*
v1[i]表示该乘积表达式第i个因子的权重，对应于具体问题的每个物品的价值或者权重。
s[i]表示该乘积表达式第i个因子的起始系数，对应于具体问题中的每个物品的最少个数，即最少要取多少个。
e[i]表示该乘积表达式第i个因子的终止系数，对应于具体问题中的每个物品的最多个数，即最多要取多少个。
*/
/*1.定义并初始化模板中的三个变量*/
int v1[N], s[N], e[N];
int i, j, m;//循环变量
for (int i = 1; i <= n; i++)
{
//v1[0]=0.s[0]=0.e[0]=0用不到，不需要管理
v1[i] = arr[i - 1];
s[i] = 0;
e[i] = 1;
}
//计算最高次数MAX = 最高次数
int MAX = 0;
for (i = 1; i <= n; i++)
MAX += v1[i] * e[i];
//a和b用于记录运行结果
int *a = new int[MAX + 1];//a计算结果
int *b = new int[MAX + 1];//b为中间结果
for (i = 0; i <= MAX; i++)
{
a[i] = 0;
b[i] = 0;
}
a[0] = 1;
//下面是相乘的过程，代码很难理解!!!
for (i = 1; i <= n; i++)
{
//for(m=0;m<=MAX;m++) b[m]=0;
for (j = s[i]; j <= e[i] && j*v1[i] <= MAX; j++)
for (m = 0; m + j * v1[i] <= MAX; m++)
b[m + j * v1[i]] += a[m];
for (m = 0; m <= MAX; m++)
{
a[m] = b[m];
b[m] = 0;
}
}
/*
*程序运行至此，a[1],a[2],...,a[MAX]是x,x^2,...,x^MAX的系数
*/
//返回想要的那个结果即可
return a[v];
}
int main(int argc, char *argv[])
{
int n, v;
scanf("%d%d", &n, &v);
//arr.resize(n);
int face_value;
for (int i = 0; i < n; i++)
{
scanf("%d", &face_value);
arr.push_back(face_value);
}
printf("%d\n", ans(n, v));
return EXIT_SUCCESS;
}
4 参考文献
https://blog.csdn.net/ten_sory/article/details/59483762 https://blog.csdn.net/vsooda/article/details/7975485 https://blog.csdn.net/xiaofei_it/article/details/17042651
