标签: 生成函数

引言

本文将介绍如何 $O(n^2)$ 计算多项式求逆、取 $\exp$ 、取 $\ln$ 。

xiezheyuan2025/5/22...大约 5 分钟

集合幂级数概论

集合幂级数

定义

设全集 $U=\{1,2,\cdots,n\},\mathbf{U}=\{S\mid S\subseteq U\}$ 。定义 $U$ 上的集合幂级数 $f:\mathbf{U}\to R$ ，其中 $R$ 为一交换环。令 $f_S$ 表示 $f$ 上 $S$ 的像。

若 $f:\mathbf{U}\to R,g:\mathbf{U}\to R$ ，则定义：

$h=f+g$ ，其中 $h:\mathbf{U}\to R$ 且 $h_S=f_S+g_S$ 。类似的可以定义 $h=f-g$ 。
$h=kf$ ，其中 $h:\mathbf{U}\to R,k\in R$ ，其中 $h_S=kf_S$ ，类似的可以定义 $h=-f$ 。
$h=f\times g$ ，其中 $h:\mathbf{U}\to R$ 且 $h_S=\sum\limits_{T\subseteq S} f_Tg_{S\backslash T}$ ，即 $f,g$ 的子集卷积（不交并卷积）。
为了方便之后的表述，我们定义 $S\sqcup T$ 表示 $S,T$ 的不交并（若 $S\cap T=\varnothing$ ，则 $S\sqcup T=S\cup T$ ，否则是非法的）。
$h=f\ast g$ ，其中 $h:\mathbf{U}\to R$ 且 $h_S=\sum\limits_{A\cup B=S} f_Ag_B$ ，即 $f,g$ 的集合并卷积（OR 卷积）。
$h=f\circ g$ ，其中 $h:\mathbf{U}\to R$ 且 $h_S=f_S\cdot g_S$ ，即 $f,g$ 的逐项积。

另外还可以定义集合交卷积（AND 卷积）、集合对称差卷积（XOR 卷积）等，它们在一般的 FMT/FWT 技术中是十分重要的，不过它们在集合幂级数理论中应用较少，故不再赘述。

xiezheyuan2025/5/20...大约 37 分钟

[Hard] P5320 [BJOI2019] 勘破神机

简要题意

给定 $m$ ，记 $f(n)$ 表示用 $1\times 2$ 的骨牌覆盖 $m\times n$ 的网格的方案数。给定 $l,r,k$ ，你需要求：

xiezheyuan2025/5/5...大约 10 分钟

生成函数，卡特兰数，伯努利数与斯特林数总结

生成函数

生成函数绪论

对于函数 $f:\mathbb{N}\to\mathbb{C}$ ，定义其普通生成函数（OGF） $\mathbf{F}(z)=\sum_{i\geq 0} f(i)z^i$ ，指数生成函数（EGF） $\hat{\mathbf{F}(z)}=\sum_{i\geq 0} \frac{f(i)}{i!}z^i$ 。