sincerit 母函数（组合问题）

本文主要是介绍sincerit 母函数（组合问题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

大佬代码： https://blog.csdn.net/yu121380/article/details/79914529
https://blog.csdn.net/xiaofei_it/article/details/17042651?utm_source=blogxgwz0
有1克、2克、3克、4克的砝码各一枚，能称出哪几种重量？各有几种可能方案？
分析：我们假设x表示砝码， x的指数表示砝码的重量，这样：
1个1克的砝码可以用函数1+x表示
1个2克的砝码可以用函数1+x²表示
1个3克的砝码可以用函数1+x³表示
1个4克的砝码可以用函数1+x⁴表示
因为每种砝码只有一个，所以1是表示对该种砝码不取。
几种砝码组合可以称重的情况，可以用以上几个函数的乘积表示：
(1+x)(1+x²)(1+x³)(1+x⁴)
所有组合的情况就是展开后的式子：
1 + x + x² + 2x³ +2x ⁴ + 2x ⁵ + 2x ⁶ + 2x ⁷ + x ⁸ + x ⁹ + x ¹⁰
从上面的函数(母函数)知道可称出从1克到10克的重量，系数便是各种重量的方案数

有2个骰子投掷出6点，共有多少种情况
分析：
我们可以设想骰子出现的点数1， 2， 3， 4， 5, 6和 t ， t² ， t³ ，t ⁴ ，t ⁵ ，t ⁶对应起来，则第一个骰子可能出现的点数就与(t+t²+t³+t ⁴+t ⁵+t ⁶)中的t的各次幂一一对应。
若两个骰子(t+t²+t³+t ⁴+t ⁵+t ⁶) * (t+t²+t³+t ⁴+t ⁵+t ⁶) = t²+2t³+3t⁴+4t⁵+…中的t⁶的系数为5，显然组成6点的可能有1+5，2+4，3+3, 4+2，5+1这5种方案数

Ignatius and the Princess III
杭电的整数划分母函数实现
输入的n相当于n种砝码(1~n)且每一种有无数多个

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
int sup[150];
int temp[150];
int main() {int n;while (cin >> n) {// 初始化第一个大括号for (int i = 0 ; i <= n; i++) {sup[i] = 1;temp[i] = 0;}// 还剩下n-1个大括号，，且从第2个开始for (int i = 2; i <= n; i++) {// 遍历当前结果多项式的每一项for (int j = 0; j <= n; j++) {for (int k = 0; k + j <= n; k+=i) {  // 遍历当前大括号的每一项temp[j+k] += sup[j];}}for (int j = 0 ; j <= n; j++) {sup[j] = temp[j];temp[j] = 0;}}printf("%d\n", sup[n]); }return 0;
}

#include <iostream>    
using namespace std;        
const int mx = 1000;     
// sup是保存多项式的数组，sup[n]中的值代表xn的系数  
// temp是临时多项式，保存相乘的临时中间情况    
int sup[mx], temp[mx];     
/* 
程序始终只计算两个多项式之间的乘积，多个多项式的情况 
先计算前两个的乘积，将结果作为第一个多项式，再与第三个相乘 
依次类推，sup始终存放当前运算后的结果然后作为被乘多项式， 
*/    
int main()    
{     int target;   //  目标重量， 比如上面的例子里就是10，要<max的值  int i, j, k;    while(cin >> target)    {    for(i=0; i<=target; ++i)       {    sup[i] = 1;     
//初始化第一个多项式，也就是用1g砝码的多项式,  
//注意如果题目没给1g的砝码那么就不能++i，而要加上砝码的质量  temp[i] = 0;    
//将临时区清空，无论第一个多项式质量是几都要全部置零  }    for(i=2; i<=target; ++i)     
// 生成后续的第i个多项式，此题中是2g，i从2开始。  
//如果砝码的值不是规律增长，i可能需要取决于输入  {    for(j=0; j<=target; ++j)     
// 遍历当前结果多项式的每一项（当前结果的第j项）与第i个多项式相乘，  for(k=0; k+j<=target; k+=i)   // 每一个系数都为1就加sup[j] 
// 遍历第i个多项式的每一项，此处构造用小砝码组成大砝码的多项式  {    temp[j+k] += sup[j];    
//幂运算，注意理解  }    for(j=0; j<=target; ++j)      
// 将临时的结果覆盖当前结果，同时把临时结果置零，为下次做准备  {    sup[j] = temp[j];    temp[j] = 0;    }    }    cout << sup[target] << endl;  //输出结果  }    return 0;    
}

Big Event in HDU
一般动态规划过不了

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(array, value) memset(array, value, sizeof(value));
#define N 2500005
int dp[N];
// dp[j]背包容量为j时的最大价值
// 转移方程
// 初始化条件 dp[0] = 0
int num[N];
int main() {int n, v, m;while (cin >> n) {if (n <= 0) break;int a, b, k = 0, sum = 0;while (n--) {cin >> a >> b;while (b--) {num[k++] = a;sum += a;}}dp[0] = 0;int V = sum / 2;for (int i = 0; i < k; i++) {for (int j = V; j >= num[i]; j--) {dp[j] = max(dp[j], dp[j-num[i]]+num[i]);}}sum - dp[V] > dp[V] ? printf("%d %d\n", sum-dp[V], dp[V]) : printf("%d %d\n", dp[V], sum-dp[V]);}return 0;
}

母函数： https://blog.csdn.net/jk13171217/article/details/38303111
题意相当于有n种砝码，每种砝码重量是weight[i], 并且每一种砝码的个数是number[i]，求把这n个砝码平均分两堆，第一堆重量大于等于第二堆

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX 250005
#define N 200
int number[N], weight[N], sup[MAX], temp[MAX];
int main() {int n, v, m;while (cin >> n && (n >= 0)) {int k = 0, sum = 0;while (n--) {cin >> weight[k] >> number[k];sum += weight[k] * number[k];k++;}int V = sum / 2;memset(sup, 0, sizeof(sup));memset(temp, 0, sizeof(temp));// 第一个大括号(1 + x^weight + x^2weight + .. +x^number[k]*weight) for (int i = 0; i <= number[0]; i++)sup[weight[0] * i] = 1;// 从第二个大括号起 (1 + x^weight[1] + x^2weight[1] + ...x^number[1]weight[1]); for (int i = 1; i < k; i++) {for (int j = 0; j <= V; j++) {// 无论多少个k x^k*weight[i]的系数都为1,就如(1+x^2+x^4+x^6+x^8) 两克的砝码有四个一样 for (int k = 0; k*weight[i] <= V && k <= number[i]; k++) // k是第i种砝码的个数temp[k*weight[i]+j] += sup[j];}for (int j = 0; j <= V; j++) {sup[j] = temp[j];temp[j] = 0;} }// 并不是所有的重量都可以凑出,所以就是一半以下得到第一个能组合出的重量的系数说明该重量就是答案 int i;for (i = V; i >= 0; i--) if (sup[i]) break;printf("%d %d\n", sum-i, i); }return 0;
}

Square Coins
题意：相当于有17种砝码，每一种砝码的重量为1²， 2²， 3²， … 17²，每一种砝码有无限多个
问给定一个重量n，问凑成这个重量的方案数是多少?
(1+t+t²+t³+…+tⁿ)(1+t+t⁴+t^{2 * 4}+t^{3 * 4}…+tⁿ) (1+t+t⁹+t^{2 * 9}+t^{3 * 9}…+tⁿ)…(1+t+t¹⁷+t^{2 * 17}+t^{3 * 17}…+tⁿ)
有17个大括号
母函数：

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
int sup[1000], temp[1000];
int coin[20];
int main() {int n;while (cin >> n, n) {for (int i = 1; i <= 17; i++) coin[i] = i*i;memset(sup, 0, sizeof(sup));memset(temp, 0, sizeof(temp));// 第一个大括号 虽然有无限多个但只要初始化到相等的重量就可以 for (int i = 0; i <= n; i++) sup[i] = 1;// 还有16个大括号 for (int i = 2; i <= 17; i++) {// 遍历当前结果的每一项for (int j = 0; j <= n; j++) {// k表示coin[i]的个数 这个循环是遍历第i个大括号里的每一项 for (int k = 0; k*coin[i]+j <= n; k++) {temp[k*coin[i]+j] += sup[j];}}for (int j = 0; j <= n; j++) {sup[j] = temp[j];temp[j] = 0;}}cout << sup[n] << "\n"; }return 0;
}

动态规划解法–完全背包
dp[i][j] 表示前i种硬币能组成纸币数为j的方案总数
对于第k种硬币当手中有j-k个硬币的方案数为dp[i-1][j-k]种时再加k个硬币就能组成纸币j的方案数
转移方程： dp[i][j] = dp[i][j] + dp[i-1][j-coin[k]];
初始化条件 dp[1~n][0] = dp[0][1~n] = 0;
换成一维数组 dp[0] = 1; 表示刚好能换成硬币 dp[4-4] = 1刚好有一个为硬币为4的换成纸币种类数为1，相当于递归的出口

#include <stdio.h>
#include <string.h>
int dp[1000];
int coin[20];
int main() {int n;for (int i = 1; i <= 17; i++) coin[i] = i * i;while (scanf("%d", &n), n) {memset(dp, 0, sizeof(dp)); // 除了dp[0]=1外其他要初始化为0 dp[0] = 1; // 表示刚好能换成硬币 for (int i = 1; i <= 17; i++) {for (int j = coin[i]; j <= n; j++) {dp[j] = dp[j] + dp[j-coin[i]];}}printf("%d\n", dp[n]); }return 0;
}

2082 找单词
输入的26个数字是各个砝码的数量，而各个砝码的重量就是对应的1~26
求小于等于50以下的所有重量的组合总数

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
ll sup[100], temp[100];
ll p[30];
int main() {int n;cin >> n;while (n--) {for (int i = 1; i <= 26; i++) cin >> p[i];  // 代表个数 memset(temp, 0, sizeof(temp));memset(sup, 0, sizeof(sup));sup[0] = 1;for (int i = 1; i <= 26; i++) { // 同时i代表每种砝码重量 for (int j = 0; j <= 50; j++) {for (int k = 0; k <= p[i] && k * i + j <= 50; k++) {  // 发现k<=p[i]不能少 temp[k*i+j] += sup[j];}}for (int j = 0; j <= 50; j++) {sup[j] = temp[j];temp[j] = 0;}}ll sum = 0;for (int j = 50; j >= 1; j--) sum += sup[j];  // 因为0代表重量为0没有选砝码，所以不加上0的supcout << sum << "\n";}return 0;
}

其他方法：用混合背包

2110 Crisis of HDU

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 10000
#define MOD 10000
int sup[N+5], temp[N+5];
int weight[105], number[105];
int main() {int n;while (cin >> n, n) {int sum = 0;for (int i = 1; i <= n; i++) {cin >> weight[i] >> number[i];sum = sum + weight[i] * number[i];  // 这里蠢了一下 }if (sum % 3 != 0) {cout << "sorry\n";continue;}memset(sup, 0, sizeof(sup));memset(temp, 0, sizeof(temp));for (int i = 0; i <= number[1]; i++) sup[i*weight[1]] = 1;int V = sum / 3;for (int i = 2; i <= n; i++) {for (int j = 0; j <= V; j++) {for (int k = 0; k <= number[i] && k*weight[i]+j <= V; k++) {temp[k*weight[i]+j] =  (temp[k*weight[i]+j] + sup[j]) % MOD;}}for (int j = 0; j <= V; j++) {sup[j] = temp[j];temp[j] = 0;}}if (sup[V]) cout << sup[V];else cout << "sorry";cout << "\n";}return 0;
}

2152 Fruit
设x代表水果， x的指数代表水果的数量
则有n个大括号(1+x^min + x^(min+1) + x^(min+2) + … x^max)(1+ x^min + x^(min+1) …+x^max)…(1 + x^min + x^min+1 + x^(min+2) + …)
求指数为m的方案数

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 205
int sup[N], temp[N];
int minumber[N], mxnumber[N]; 
int main() {int n, m;while (cin >> n >> m) {for (int i = 1; i <= n; i++) cin >> minumber[i] >> mxnumber[i];memset(sup, 0, sizeof(sup));memset(temp, 0, sizeof(temp));// sup[0] = 1 原本有这个的但提交错了， 后来想到有最小值这个就不能为1了，可能最小数量不是不取for (int i = minumber[1]; i <= mxnumber[1]; i++) sup[i] = 1;for (int i = 2; i <= n; i++) {for (int j = 0; j <= m; j++) {for (int k = minumber[i]; k <= mxnumber[i] && k+j <= m; k++) {temp[k+j] += sup[j];}}for (int j = 0; j <= m; j++) {sup[j] = temp[j];temp[j] = 0;}}cout << sup[m] << "\n";}return 0;
}