#创作计划# 生成函数
2025-08-06 10:20:54
发布于：浙江
先看例题：
BZOJ3028 食物
先看数据范围，，可能会想到矩阵加速。
表示选了 件物品的方案数，很明显，对于只能选偶数类，奇数类， 的倍数类， 的倍数类，需要记录以前分别 的前缀和，我们考虑先只选这些有倍数限制的方案，因为这些可以从前面转移，而像只能选 个之类的，是一次性消耗品，发现可以最后再选。那么转移矩阵也就是 的，最后乘上 也就约等于 左右。求出 之后就可以暴力枚举剩下的食物分别选几个，再从前面转移即可。似乎能过？
但是这样还是太慢了，有没有更快又更简单不用构造转移矩阵的方法呢，有的兄弟有的，我们生成函数就可以登场了。
我们发现，假如现在选 个的方案数为 ，考虑选不选可乐的情况，那么选可乐就会变成选 个的方案数为 ；不选即为选 个的方案数为 。这个似乎很像一个乘法分配律？将选 个的方案数为 换一个形式表达：，选不选可乐的情况即为 ，将两者乘在一起变为 ，化简变为 ，发现 的幂即为选了多少个，其系数即为方案数。
那么显然有初值 ，即选 个的方案数为 。那每种方案将其转化分别变为：
- 汉堡：
- 可乐：
- 鸡腿：
- 蜜桃多：
- 鸡块：
- 包子：
- 土豆片炒肉：
- 面包：
发现乘上一个 就相当于又选了 个数，而对于有多种选择的物品，我们用加法将其加起来，之后用乘法分配律即可计算。所以答案即为上面这些式子乘在一起，取 的系数。
但是发现有一些式子是有无穷项的，无法乘在一起，所以我们考虑求出其封闭形式。
引理 ：
该引理被称为几何级数公式。证明考虑等比数列求和公式，原式可变为 ，由于 ，所以 趋近 ，故原式等于 。
这里可能有读者疑惑，可以保证 吗？生成函数研究的是 在 的邻域的情况，所以有 。
同理 。
那么重新写出：
- 汉堡：
- 蜜桃多：
- 鸡块：
- 面包：
那么最后乘法就比较简单了，这里直接给出化简之后的结果 ，但是此时我们依然不知道 的系数。
设 为实数， 为整数，则定义：
引理 ：
这个引理被称为广义牛顿二项式定理，读者自证不难。
则原式变为：。根据定义 可以先将分子中的 提出来，变为 ，将 带入，变为 。然后继续化简：
化简完成，由此我们知道了 系数为 ，这就是生成函数的作用，能让我们快速求出某个方案数。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=10007;
int n;
inline int read(){
int t=0,f=1;
register char c=getchar();
while (c<48||c>57) f=(c=='-')?(-1):(f),c=getchar();
while (c>=48&&c<=57)t=(t<<1)+(t<<3)+(c^48),c=getchar();
return f*t;
}
void solution(){
/*
*/
}
string s;
int ksm(int x,int y){
int sum=1;
while(y){
if(y&1) sum=sum*x%mod;
x=x*x%mod;y>>=1;
}
return sum;
}
signed main(){
cin>>s;
for(int i=0;i<s.size();i++){
int x=s[i]-'0';
n=n*10+x;n%=mod;
}
n=(n+1)*(n+2)%mod*n%mod;
n=n*ksm(6,mod-2)%mod;
cout<<n<<"\n";
return 0;
}
[CEOI 2004] Sweets
依旧采用上一题的思路，考虑将 表示选 颗糖果，其系数为方案数。那么每个糖果罐的方程即为 ，代表分别选 个糖果的方案数。
发现 的值比较大，那么就将原方程转为封闭形式，设 ，则 ，两者相减有 ，故 。
则所有方程的积即为 ，由于 最大为 ，所以后面的乘积最多有 项，所以可以直接暴力合并，而前面的次方可以用类似上题使用广义牛顿二项式定理变为：，所以在不考虑后面的多项式的情况下， 的系数为 。
设后面的多项式为 ，我们考虑其中一项 对答案（即选 个糖的方案数）的贡献：。证明考虑 。具体地，将第一项 改为 ，然后就可以向后一直推下去了。
那么问题来到了求一个组合数模 的值，，显然分子可以预处理出来，设分子为 ，同时 ，因为 ，所以将 分解后，肯定每一项都包含 ，那么现在只需要将 对 取模然后除以 即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INT_MAX (1e18)
#define pr pair<int,int>
const int N=12;
const int mod=2004;
int n,l,r;
int m[N];
vector<pr > g;
inline int read(){
int t=0,f=1;
register char c=getchar();
while (c<48||c>57) f=(c=='-')?(-1):(f),c=getchar();
while (c>=48&&c<=57)t=(t<<1)+(t<<3)+(c^48),c=getchar();
return f*t;
}
void solution(){
/*
*/
}
void dfs(int dang,int sum,int sum1){
if(dang>n){
g.push_back({(sum1&1?-1:1),sum});
return;
}
dfs(dang+1,sum,sum1);
dfs(dang+1,sum+m[dang]+1,sum1+1);
}
int calc(int x,int y){
int val=1,val1=1;
for(int i=1;i<=y;i++) val1*=i;val1*=2004;
for(int i=x-y+1;i<=x;i++) val=val*i%val1;
val/=(val1/2004);
return val;
}
int solve(int xx){
int res=0;
for(pr i:g){
int x=i.first,y=i.second;
if(xx<y) continue;
res=(res+x*calc(n+xx-y,n)%mod)%mod;
}
return res;
}
signed main(){
n=read(),l=read(),r=read();
for(int i=1;i<=n;i++) m[i]=read();
dfs(1,0,0);int ans=solve(r)-solve(l-1);
ans=(ans%mod+mod)%mod;
cout<<ans<<"\n";
return 0;
}
有帮助，赞一个