#创作计划# 生成函数

ask_silently

2025-08-06 10:20:54

发布于：浙江

8阅读

0回复

0点赞

博客园食用更佳
 关注洛谷谢谢喵~

先看例题：

BZOJ3028 食物

先看数据范围， $n \le 10^{500}$ ，可能会想到矩阵加速。

$dp_i$ 表示选了 $i$ 件物品的方案数，很明显，对于只能选偶数类，奇数类， $4$ 的倍数类， $3$ 的倍数类，需要记录以前分别 $\bmod 2,3,4$ 的前缀和，我们考虑先只选这些有倍数限制的方案，因为这些可以从前面转移，而像只能选 $0 \sim 3$ 个之类的，是一次性消耗品，发现可以最后再选。那么转移矩阵也就是 $11 \times 11$ 的，最后乘上 $\log 10^{500}$ 也就约等于 $1660$ 左右。求出 $dp_n$ 之后就可以暴力枚举剩下的食物分别选几个，再从前面转移即可。似乎能过？

但是这样还是太慢了，有没有更快又更简单不用构造转移矩阵的方法呢，有的兄弟有的，我们生成函数就可以登场了。

我们发现，假如现在选 $a$ 个的方案数为 $b$ ，考虑选不选可乐的情况，那么选可乐就会变成选 $a+1$ 个的方案数为 $b$ ；不选即为选 $a$ 个的方案数为 $b$ 。这个似乎很像一个乘法分配律？将选 $a$ 个的方案数为 $b$ 换一个形式表达： $b \times x^a$ ，选不选可乐的情况即为 $(x+1)$ ，将两者乘在一起变为 $b \times x^a \times(x+x^0)$ ，化简变为 $b \times x^a + b \times x^{a+1}$ ，发现 $x$ 的幂即为选了多少个，其系数即为方案数。

那么显然有初值 $x^0$ ，即选 $0$ 个的方案数为 $1$ 。那每种方案将其转化分别变为：

汉堡： $\sum_{i=0}^{\infty} x^{2i}$
可乐： $x^0+x^1$
鸡腿： $x^0+x^1+x^2$
蜜桃多： $\sum_{i=0}^{\infty} x^{2i+1}$
鸡块： $\sum_{i=0}^{\infty} x^{4i}$
包子： $x^0+x^1+x^2+x^3$
土豆片炒肉： $x^0+x^1$
面包： $\sum_{i=0}^{\infty} x^{3i}$

发现乘上一个 $x^a$ 就相当于又选了 $a$ 个数，而对于有多种选择的物品，我们用加法将其加起来，之后用乘法分配律即可计算。所以答案即为上面这些式子乘在一起，取 $x^n$ 的系数。

但是发现有一些式子是有无穷项的，无法乘在一起，所以我们考虑求出其封闭形式。

引理 $1$ ： $\sum_{i=0}^{\infty} x^i=\dfrac{1}{1-x}(|x|<1)$

该引理被称为几何级数公式。证明考虑等比数列求和公式，原式可变为 $\dfrac{x^\infty-1}{x-1}$ ，由于 $|x|<1$ ，所以 $x^\infty$ 趋近 $0$ ，故原式等于 $\dfrac{1}{1-x}$ 。

这里可能有读者疑惑，可以保证 $|x|<1$ 吗？生成函数研究的是 $x$ 在 $0$ 的邻域的情况，所以有 $|x|<1$ 。

同理 $\sum_{i=0}^{\infty} x^{2i}=\dfrac{1}{1-x^2},\sum_{i=0}^{\infty} x^{4i}=\dfrac{1}{1-x^4}$ 。

那么重新写出：

汉堡： $\frac{1}{1-x^2}$
蜜桃多： $\frac{x}{1-x^2}$
鸡块： $\frac{1}{1-x^4}$
面包： $\frac{1}{1-x^3}$

那么最后乘法就比较简单了，这里直接给出化简之后的结果 $x \times (x-1)^{-4}$ ，但是此时我们依然不知道 $x^n$ 的系数。

设 $\alpha$ 为实数， $i$ 为整数，则定义：

${\alpha \choose i}=\begin{cases}0,&(i<0)\\1,&(i=0)\\\frac{\alpha(\alpha-1)\cdots(\alpha-i+1)}{i!},&(i>0)\end{cases}$

引理 $2$ ： $(x+y)^{\alpha}=\sum_{i=0}^{\infty} {\alpha \choose i} x^i y^{\alpha-i}$

这个引理被称为广义牛顿二项式定理，读者自证不难。

则原式变为： $x \times \sum_{i=0}^{\infty} {-4\choose i}x^i(-1)^{-4-i}$ 。根据定义 $\alpha\choose i$ 可以先将分子中的 $(-1)^i$ 提出来，变为 $(-1)^i \times \dfrac{(-\alpha+i-1)(-\alpha+i)\cdots-\alpha}{i!}=(-1)^i \times {{i-\alpha-1}\choose i}$ ，将 $\alpha=4$ 带入，变为 ${-4\choose i}={i+3\choose i}$ 。然后继续化简：

$\begin{aligned}&x \times \sum_{i=0}^{\infty} {-4\choose i}x^i(-1)^{-4-i}\\&= x \times \sum_{i=0}^{\infty} {i+3\choose i} x^i(-1)^{-4-i}(-1)^i\\&=\sum_{i=0}^{\infty} {i+3\choose i} x^{i+1}\\&=\sum_{i=1}^{\infty} {i+2\choose 3}x^i\\&= \sum_{i=1}^{\infty} \dfrac{i(i+1)(i+2)}{6} \times x^i \end{aligned}$

化简完成，由此我们知道了 $x^n$ 系数为 $n(n+1)(n+2)$ ，这就是生成函数的作用，能让我们快速求出某个方案数。

#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

依旧采用上一题的思路，考虑将 $x^k$ 表示选 $k$ 颗糖果，其系数为方案数。那么每个糖果罐的方程即为 $\sum_{j=0}^{m_i} x^j$ ，代表分别选 $0,1,\cdots,m_i$ 个糖果的方案数。

发现 $m_i$ 的值比较大，那么就将原方程转为封闭形式，设 $f_i=\sum_{j=0}^{m_i} x^j$ ，则 $f_i \times x =\sum_{j=1}^{m_i+1} x^j$ ，两者相减有 $f_i \times (x-1)=x^{m_i+1}-1$ ，故 $f_i=\dfrac{x^{m_i+1}-1}{x-1}$ 。

则所有方程的积即为 $(1-x)^{-n} \times \prod_{i=1}^n (1-x^{m_i+1})$ ，由于 $n$ 最大为 $10$ ，所以后面的乘积最多有 $2^{10}=1024$ 项，所以可以直接暴力合并，而前面的次方可以用类似上题使用广义牛顿二项式定理变为： $\sum_{i=0}^{\infty}{i+n-1\choose n-1} x^i$ ，所以在不考虑后面的多项式的情况下， $x^i$ 的系数为 ${i+n-1\choose n-1}$ 。

设后面的多项式为 $g(x)=a_1x^{b_1} + a_2x^{b_2}+\cdots+a_px^{b_p}$ ，我们考虑其中一项 $j$ 对答案（即选 $1\sim a$ 个糖的方案数）的贡献： $a_j \times \sum_{i=0}^{a-b_j} {i+n-1\choose i}=a_j \times {n+a-b_j \choose a-b_j}=a_j \times {n+a-b_j \choose n}$ 。证明考虑 ${n \choose m}={n-1 \choose m-1}+{n-1 \choose m}$ 。具体地，将第一项 ${n-1\choose 0}$ 改为 ${n\choose 0}$ ，然后就可以向后一直推下去了。

那么问题来到了求一个组合数模 $2004$ 的值， ${n \choose m}=\dfrac{\frac{n!}{(n-m)!}}{m!}$ ，显然分子可以预处理出来，设分子为 $x$ ，同时 $x=2004 \times p \times m! + q \times m!(q<2004)$ ，因为 $m!|x$ ，所以将 $x$ 分解后，肯定每一项都包含 $m!$ ，那么现在只需要将 $x$ 对 $2004 \times m!$ 取模然后除以 $m!$ 即可。

#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;
}

有帮助，赞一个

去预览

0/2000

全部评论 2

cjdstttttt
生成函数做法难度是蓝吗

2025-08-06 来自浙江
0
- ask_silently
  回复cjdstttttt
  那主要看你做的是什么类型的了，有的题可能生成函数只是其中的一个步骤，但是生成函数一般都是紫吧
  
  2025-08-06 来自浙江
  0
- cjdstttttt
  回复ask_silently
  ok
  
  2025-08-06 来自浙江
  0
cjdstttttt
%%%

2025-08-06 来自浙江
0

BZOJ3028 食物

[CEOI 2004] Sweets

全部评论 2

热门讨论