普通型生成函数

这个是序列普通生成函数。

Part I 基础识别

您通常能把一个序列 \(a\) 刻画为 \(F(x)=\sum_{n}a_nx^n\) 的形式幂级数，这就是它的 OGF。

OGF 也有无穷序列的覆盖，例如序列 \(\{1,3,5,7,9,...\}\) 的 OGF 为 \(\sum_{n\geq 0}(2n+1)x^n\)。

一般来说，您可以通过一个序列的简洁通项公式作为定位 OGF 的依据。

它的加法和乘法都与 poly 相同。

Part II 聚焦区域

一般来说，您可以适时地把 OGF 转化封闭形式，找到更多的解题线索。

例如 FIB/等比数列 都可以利用方程进一步定位。

这里给出两个组合数序列 \(a_n={m\choose n}\) 和 \(a_n={n+m\choose n}\) 封闭形式的实例。

第一个利用 binom ，得到 \((1+x)^m\)。

另一个可以考虑使用归纳法证明：

\[m=0\to f_0(x)=(1-x)^{-1}\]

\[\begin{aligned}m>0\to \{(1-x)^{m+1}\}^{-1}&=\{(1-x)^{m}\}^{-1}f_0(x)\\&=\sum_{n>0}x^n\sum_{i=0}^n{m+i-1\choose i}\\&=\sum_{n>0}{m+n\choose n}x^n\end{aligned}\]

还可以利用一些求导的手段定位，您应该比较容易掌握这些。

Part III 特殊覆盖

牛顿二项式定理

在 \(r\) 的复数域上定义了 binom 的成立，

「CEOI2004」Sweet

利用 OGF 列出答案：

\[ G(x)=\prod_{i=1}^{n}F_i(x)=\prod_{i-1}^{n}\frac{1-x^{m_i+1}}{1-x} \]

我们暴力展开分子，对于分母，利用 binom：

\[(1-x)^{-n}=\sum_{i\geq 0}{-n\choose i}(-x)^i=\sum_{i\geq 0}{n+i-1\choose i}x^i\]

它的前缀和容易 \(O(1)\) 计算，于是我们枚举分子中 \(x^k\) 项的系数，求和即可 \(O(b)\) 求出答案了。

Part IV 地图资源

暂无