Polynomial_Count

基本是复读 cmd 的博客。。。因为这玩意我一点不会。。。所以大概算是学习笔记。。。

虽然 Jwz 和我说这玩意不太可能考，但我可能这辈子就学这么一次。。。

前置：基础基础基础多项式基础工业（这是一篇连 MTT 都没有的屑工业博文）。

深必的东西：

1. 广义二项式系数，当 $n\in \mathbb{R}$，$m\in \mathbb{N}$ 时，有：

$$\binom{n}{m}=\dfrac{n!}{m!(n-m)!}=\dfrac{n(n-1)\cdots (n-m+1)}{m!}$$

2. 广义二项式定理，当 $a\in \mathbb{R}$ 时：

$$(1+x)^a=\sum_{i=0}^{\infty}\binom{a}{i}x^i$$

3. 恒等式：

$$\binom{n}{k}=\binom{n}{n-k}$$

$$\binom{n}{k}=(-1)^k\binom{k-n-1}{k}$$

一、生成函数引入

1. 斐波那契数列的生成函数：

   斐波那契数列定义 $f_0=0,f_1=1$。

   $$F(x)=x+xF(x)+x^2F(x)$$

   $$F(x)=\dfrac{x}{1-x-x^2}$$

2. 1 元，2 元，5 元支付 $n$ 元的方案数：

   $$F_1(x)=1+x+x^2+\cdots=\dfrac{1}{1-x}$$

   $$F_2(x)=1+x^2+x^4+\cdots=\dfrac{1}{1-x^2}$$

   $$F_5(x)=1+x^5+x^{10}+\cdots=\dfrac{1}{1-x^{10}}$$

   $$G(x)=F_1(x)F_2(x)F_5(x)$$

生成函数分析计数问题的步骤：先将问题用生成函数刻画，再用处理幂级数的技巧得到答案。

二、轻量级推导

1. 已知系数的若干幂级数：

   • $\langle 1, 1,1,\cdots\rangle$ 的生成函数是 $\dfrac{1}{1-x}$
   • $\langle 1,a,a^2,\cdots\rangle$ 的生成函数是 $\dfrac{1}{1-ax}$
   • $F(x)=1+x^k+(x^k)^2+\cdots=\dfrac{1}{1-x^k}$
   • $F(x)=1+cx^k+(cx^k)^2+\cdots=\dfrac{1}{1-cx^k}$
   • $\langle \binom{n}{0},\binom{n}{1},\binom{n}{2},\cdots\rangle$ 的生成函数是 $(1+x)^n$（广义二项式定理）
   • $\langle \binom{n}{0},-\binom{n}{1},\binom{n}{2},\cdots\rangle$ 的生成函数是 $(1-x)^n$（把上面那个 $x$ 变成 $-x$）
   • $\langle\binom{n}{0},\binom{n+1}{1},\binom{n+2}{2},\cdots\rangle$ 的生成函数是 $(1-x)^{-n-1}$（用上面的恒等式）

   我们要做的就是通过封闭形式反推回数列。

2. 斐波那契数列（生成函数求通项）：

   $$F(x)=\dfrac{x}{1-x-x^2}$$

   我们知道这是个常系数齐次递推，所以很显然最后的通项会是指数求和的形式，而我们又知道 $\dfrac{1}{1-cx^k}$ 这个东西，所以我们想办法往上面靠。

   裂项裂项裂项（根据二次）：

   $$\dfrac{1}{1-x-x^2}=\dfrac{A}{1-\alpha x}+\dfrac{B}{1-\beta x}$$

   有方程：

   $$(1-\alpha x)(1-\beta x)=1-x-x^2$$

   得到：

   $$\alpha=\dfrac{1+\sqrt{5}}{2},\beta=\dfrac{1-\sqrt{5}}{2}$$

   又有方程：

   $$A(1-\beta x)+B(1-\alpha x)=x$$

   解得：

   $$A=\dfrac{\sqrt{5}}{5},B=-\dfrac{\sqrt{5}}{5}$$

   代回去：

   $$F(x)=\dfrac{x}{1-x-x^2}=\dfrac{\sqrt{5}}{5}(\dfrac{1}{1-\frac{1+\sqrt{5}}{2}x}-\dfrac{1}{1-\frac{1-\sqrt{5}}{2}x})$$

   拆回幂级数的形式：

   $$\begin{aligned}F(x)=\dfrac{\sqrt{5}}{5}[(1+\dfrac{1+\sqrt{5}}{2}x+(\dfrac{1+\sqrt{5}}{2})^2x^2+\cdots)
   \\
   +(1+\dfrac{1-\sqrt{5}}{2}x+(\dfrac{1-\sqrt{5}}{2})^2x^2+\cdots)]\end{aligned}$$

   这岂不是显然的不能再显然了？？？

   $$f_n=\dfrac{\sqrt{5}}{5}[(\dfrac{1+\sqrt{5}}{2})^n-(\dfrac{1-\sqrt{5}}{2})^n]$$

   深必应用：求 $\sum_{i=1}^nf_i^k$，随便推推就能得到 $r^k\sum_{j=0}^k\binom{k}{j}\sum_{i=1}^n(a^jb^jb^{-k})^i$（其中 $r=\dfrac{\sqrt{5}}{5}$，$a=\alpha$，$b=\beta$）。

3. 特征方程（求解常系数齐次递推，隔壁 MO 一般解二阶，因为阶数一高就要求高阶方程了）

   和生成函数关系不大，但是 MO 的用了都说好！

   求解这玩意和求解微分方程非常相似！

   但我们先鸽掉这种理解！（咕咕咕）

   定理：

   对于常系数齐次递推 $h_n=a_1h_{n-1}+\cdots+a_kh_{n-k}$（$a_k\not=0$，$n\ge k$），其特征方程为：

   $$x^k-a_1x^{k-1}-a_2x^{k-2}-\cdots-a_k=0$$

   若该多项式方程有 $k$ 个不同的根 $q_1,q_2,\cdots,q_k$，则：

   $$h_n=c_1q_1^n+c_2q_2^n+\cdots+c_kq_k^n$$

   无论给定怎样的初始数列 $h_1,h_2,\cdots,h_{k-1}$，都存在常数 $c_1,c_2,\cdots,c_k$，且数列唯一。

   特征方程的 $k$ 个根称为特征根，通项成立的条件是特征根互不相同。

   想要证明这个定理需要用到线性代数的一些知识，详细证明可以参考《组合数学》。（咕不咕？咕哉，咕哉。）

   更常见的二阶情况，譬如：

   已知 $f_0$，$f_1$，求解 $f_n=af_{n-1}+bf_{n-2}$ 的通项。

   根据上面的定理，我们可以得到特征方程：

   $$x^2-ax-b=0$$

   其特征根为：

   $$q_1=\dfrac{a+\sqrt{a^2+4b}}{2},q_2=\dfrac{a-\sqrt{a^2+4b}}{2}$$

   则有：

   $$f_n=c_1q_1^n+c_2q_2^n$$

   代入 $n=0$ 和 $n=1$ 的情况把 $c_1$ 与 $c_2$ 解出来，然后就能得到通项啦！

4. 构造幂级数技巧：

   • 平移：$[x^n]x^tF(x)=f_{n-t}$
   • 拉伸：$F(x^k)$（会在中间空出来 $k-1$ 个 0）

5. 生成函数封闭形式的获取：

   已知数列 ${f}$ 和递推系数 ${c}$，容易知道在常系数齐次递推下它能满足：$\sum_{i=0}^kc_if_{n-i}=0$（就是特征方程）。

   设 $F(x)$ 为 ${f}$ 的生成函数。

   考虑使用递推式凑出次数到达 $k$ 的部分。

   构造生成函数：

   $$F_t(x)=c_tx^t(F(x)-\sum_{i=0}^{k-t-1}f_ix^i)$$

   易知 $[x^n]F_t(x)=c_tf_{n-t}$，这恰好是定义式所需要的（这里对于任意 $n\ge k$）。

   很显然 $\sum_{i=0}^kc_if_{n-i}=0$（同样对于任意 $n\ge k$），于是就有了 $\sum_{i=0}^kF_t(x)=0$，即：

   $$\sum_{t=0}^kc_tx^t(F(x)-\sum_{i=0}^{k-t-1}f_ix^i)=0$$

   移项：

   $$(\sum_{t=0}^kc_tx_t)F(x)=\sum_{t=0}^k(c_tx^t\sum_{i=0}^{k-t-1}f_ix^i)$$

   左边有 ${c}$ 的生成函数，设为 $C(x)$，右边的余项次数小于 $k$，设为 $P(x)$。

   即 $C(x)F(x)=P(x)$，即 $F(x)=\dfrac{P(x)}{C(x)}$。（已经得到了封闭形式）

6. 分式分解

   求形如 $F(x)=\dfrac{P(x)}{C(x)}$ 的系数的通项。

   所以谁会一般的分式分解啊？？？

   找出 $k$，$p$，使得 $C(x)\mid (1-x^k)^p$，记 $A(x)=\dfrac{(1-x^k)^p}{C(x)}$。

   则 $F(x)=\dfrac{A(x)P(x)}{(1-x^k)^p}$。

   例子：求 $F(x)=\dfrac{1}{(1-x)(1-x^2)(1-x^5)}$ 的系数。

   因为 $(1-x)(1-x^2)(1-x^5)\mid (1-x^{10})^3$（我也不知道怎么找的）：

   $$\begin{aligned}A(x)&=\dfrac{(1-x^{10})^3}{(1-x)(1-x^2)(1-x^5)}\\ &=
   x^{22}+x^{21}+2x^{20}+2x^{19}+3x^{18}+4x^{17}+5x^{16}\\
   & +6x^{15}+7x^{14}+8x^{13}+7x^{12}+8x^{11}\\
   &+7x^{10}+8x^9+7x^8+6x^7+5x^6\\ &+4x^5+3x^4+2x^3+2x^2+x+1
   \end{aligned}$$

   然后有：

   $$f_n=[x^n]\dfrac{A(x)}{(1-x^{10})^3}=\sum_{i+j=n}a_i[x^j]\dfrac{1}{(1-x^{10})^3}$$

   注意到 $[x^n]\dfrac{1}{(1-x^c)^k}=[c\mid n]\dbinom{n/c+k-1}{n/c}$，所以：

   $$f_n=\sum_{i=0}^{22}a_i[10\mid (n-i)]\dbinom{(n-i)/10+2}{(n-i)/10}$$

7. 卡塔兰数

   定义 $c_0=1$，$c_n$ 表示 $n$ 对括号的合法序列数（$n>1$）。

   容易得到递推式：

   $$c_{n+1}=\sum_{i=0}^nc_ic_{n-i}$$

   组合理解这东西：第 $n+1$ 对括号放在前面，把剩下 $n$ 堆括号分成两份，一份放在第 $n+1$ 对括号里，另外一份放在其右边。

   这个式子 $O(n^2)$ 不多说了。

   这玩意贼像卷积，我们拿 Catalan 数的生成函数自卷一下：

   $$[x^n]C^2(x)=\sum_{i=0}^nc_ic_{n-i}=c_{n+1}$$

   相当于系数整体左移，也就是说 $C^2(x)=\dfrac{C(x)-1}{x}$。

   解出来 $C(x)=\dfrac{1\pm\sqrt{1-4x}}{2x}$。

   关于根的取舍：

   显然 $\lim_{x\rightarrow 0} C(x)=c_0=1$，然而取正号时是 $C(x)=\infty$，取符号时 $C(x)=1$（洛必达）（二者是等量无穷小，收敛）。

   数列如果存在必然会有一根正确，一般情况下把错的给舍弃掉就完事了。

   所以：

   $$C(x)=\dfrac{1-\sqrt{1-4x}}{2x}$$

   由广义二项式定理：

   $$\begin{aligned}\sqrt{1-4x}&=(1-4x)^{\frac{1}{2}}\\
   &= \sum_{i=0}^{\infty}\binom{\frac{1}{2}}{i}(-4x)^i\\
   &= 1+\sum_{i\ge 1}\dfrac{\frac{1}{2}\times (-\frac{1}{2})\times\cdots \times(\frac{3-2i}{2})}{i!}(-4x)^i\\
   &= 1+\sum_{i\ge 1}(-1)^{i-1}\dfrac{1\times 3\times 5\times\cdots\times (2i-3)}{2^ii!}(-4x)^i\\
   &=1-\sum_{i\ge 1}\dfrac{1\times 3\times 5\times \cdots\times (2i-3)}{i!}(2x)^i\\
   &=1-\sum_{i\ge 1}\dfrac{1\times 2\times 3\times\cdots \times (2i-3)\times (2i-2)}{2\times 4\times \cdots\times (2i-2)\times i!}(2x)^i\\
   &= 1-\sum_{i\ge 1}\dfrac{(2i-2)!}{(i-1)!i!2^{i-1}}(2x)^i\\
   &= 1-2\sum_{i\ge 1}\dfrac{(2i-2)!}{(i-1)!i!}x^i\end{aligned}$$

   代入 $C(x)$，则有：

   $$\begin{aligned}C(x)&=\dfrac{1}{2x}(2\sum_{n\ge 1}\dfrac{(2n-2)!}{(n-1)!n!}x^n)\\
   &=\sum_{n\ge 1}\dfrac{(2n-2)!}{(n-1)!n!}x^{n-1}\\
   &=\sum_{n\ge 0}\dfrac{(2n)!}{n!(n+1)!}x^n\\
   &=\sum_{n\ge 0}\dfrac{\binom{2n}{n}}{n+1}x^n\end{aligned}$$

   于是就有了熟悉的：

   $$c_n=\dfrac{1}{n+1}\binom{2n}{n}$$

8. 前缀和

   如 ${f}$ 的前缀和 ${s}$，我们有 $s_n=\sum_{i=0}^nf_i$。

   那么对于 ${s}$ 的生成函数：

   $$\begin{aligned}
   S(x)
   &=\sum_{n\ge 0}s_nx^n
   \\
   &=\sum_{n\ge 0}(\sum_{i=0}^nf_i)x^n
   \\
   &= \sum_{i\ge 0}f_i\sum_{n\ge i}x^n
   \\
   &=\sum_{i\ge 0}f_i\dfrac{x_i}{1-x}\\
   &=\dfrac{1}{1-x}\sum_{i\ge 0}f_ix^i
   \\
   &= \dfrac{1}{1-x}F(x)
   \end{aligned}$$

   因此，要求一个数列前缀和的生成函数，将其生成函数乘上 $(1-x)^{-1}$ 即可。

9. P4921 [MtOI2018]情侣？给我烧了！

10. 一个排列计数问题：对 $[1,n]$ 内的整数进行排列，满足相差 1 的数不会相邻，问方案数。

    咕。这个不会。。。

三、生成函数组合计数初步

组合对象指满足某些性质的可数对象，组合对象组成的集合称为组合类。

对于组合类 $\mathcal{A}$，其中每个对象 $a\in \mathcal{A}$，都被定义了一个“大小” $|a|$，可能代表节点个数，串长等。

将所有大小为 $n$ 的计数对象记作 $\mathcal{A_n}$。

定义计数序列 $a_n=|\mathcal{A_n}|$，即大小为 $n$ 的组合对象的总数目，通常有限。

我们的任务通常是求出 $a_n$。

约定使用字母 $\mathcal{ABCDEFG}$（$\LaTeX$ 下的 \mathcal{}）表示组合类。

1. 笛卡尔积

   定义 ${(a_1,a_2,\cdots,a_n)\mid a_1\in A_1,a_2\in A_2,\cdots,a_n\in A_n}$ 为集合 $A_1,A_2,\cdots,A_n$ 的笛卡尔积，记作 $A_1\times A_2\times \cdots \times A_n$。

   满足性质 $|A\times B|=|A|\times|B|$，即乘法原理。

   对于组合对象 $a$，$b$ 的组合 $(a,b)$，定义 $|(a,b)|=|a|+|b|$。

2. OGF

   给出两个比较显然的经典 OGF：

   • $\langle 0,1,\dfrac{1}{2},\dfrac{1}{3},\cdots\rangle$ 的 OGF 是 $\ln \dfrac{1}{1-x}=-\ln(1-x)$
   • $\langle 1,1,\dfrac{1}{1!},\dfrac{1}{2!},\cdots\rangle$ 的 OGF 是 $e^x$

   下面是组合意义：

   • 加法代表不相交集合的并：若有组合类 $\mathcal{A}$，$\mathcal{B}$，令 $\mathcal{D}=\mathcal{A}\times \mathcal{B}$，即笛卡尔积。

     然后它满足加法卷积，所以我们可以知道 $D(x)=A(x)B(x)$。

     实际上它就是计数背包的形式。

   例一：P2000 拯救世界

   • 加法卷积，但是要 NTT

   例二：UVA12298 Super Poker II

   • 刘汝佳书上（可能是唯一的）FFT 练习题

   • 加法卷积，和上面的差不多，因为都是在处理背包

   例三：P4551 [国家集训队]整数的lqp拆分

   • 不会

   • 可以找到答案序列的生成函数：$F(x)=\dfrac{x}{1-x-x^2}$，$G(x)=\sum_{m=0}F^m(x)=\dfrac{1}{1-F(x)}$。部分分可以直接全家桶艹上去。

   例四：CF438E The Child and Binary Tree

   • 从 DP 到生成函数

   例五：CF917D Stranger Trees

   • 不会

   例六：P4389 付公主的背包

   • 乘积用 $\ln$ 转换为加法再 $\exp$ 回去的自然思路

   • 经典无标号计数

3. EGF

   定义 ${f}$ 的 EGF 是：

   $$F(x)=\sum_{i=0}^{\infty}f_i\dfrac{x^i}{i!}$$

   定义两个 EGF 的乘积为二项卷积（并非严谨名称），满足：

   $$(f*g)(k)=\sum_{i+j=k}\binom{k}{i}f_ig_j$$

   其实非常显然：

   $$\dfrac{(f*g)(k)}{k!}=\sum_{i+j=k}\dfrac{f_i}{i!}\dfrac{g_j}{j!}$$

   显然 $j=k-i$：

   $$(f*g)(k)=\sum_{i+j=k}\dfrac{k!}{i!(k-i)!}f_ig_j=\sum_{i+j=k}\binom{k}{i}f_ig_j$$

   常见 EGF：

   • $\langle 1,1,1\cdots \rangle$ 的 EGF 是 $e^x$

   • $\langle 1,-1,1,-1,\cdots\rangle$ 的 EGF 是 $e^{-x}$

   • $\langle 1,c,c^2,c^3\cdots\rangle$ 的 EGF 是 $e^{cx}$

   • $\langle 1,0,1,0,1\cdots\rangle$ 的 EGF 是 $\dfrac{e^x+e^{-x}}{2}$（前两个加起来除以 2）

   • $\langle 1,a,a^{\underline{2}},a^{\underline{3}},\cdots\rangle$ 的 EGF 是 $(1+x)^a$（展开后就是二项式定理的基本形式）

   关于组合意义：

   • 不相交集合的并：

     仍然有 $\mathcal{C}=\mathcal{A}+\mathcal{B}\Rightarrow C(x)=A(x)+B(x)$。

   • 笛卡尔积（有标号对象的）

   例一：染色，红蓝绿涂长度为 $n$ 的纸条，使红色和蓝色的个数都为偶数，求方案数。

   绿色的 EGF：$F(x)=e^x$。

   红色和蓝色的 EGF 分别为：$G(x)=\dfrac{e^x+e^{-x}}{2}$。

   相乘即答案序列 EGF：

   $$H(x)=(\dfrac{e^x+e^{-x}}{2})^2e^x=\dfrac{e^{3x}+2e^x+e^{-1}}{4}$$

   拆系数得到：

   $$h_n=\dfrac{3^n+2+(-1)^n}{4}$$

   例二：有 $n$ 种颜色，每种颜色都有可染次数，求染一条长度为 $m$ 的纸带的方案数。

   一个 $m$ 次最多的颜色的 EGF：$F(x)=\sum_{i=0}^{m}\dfrac{x^i}{i!}$。

   全部乘起来就是答案序列的 EGF。

   看不懂，咕了。

4. PGF

   概率生成函数的定义：

   $$F(z)=\sum_{i=0}^{\infty}P(X=i)z^i$$

   显然 $F(1)=1$。

   还有 $E(X)=\sum_{i=0}^{\infty}P(X=i)i=F’(1)$。

   进一步扩展就是 $E(x^{\underline{k}})=F^{(k)}(1)$。

   看不下去了。。。直接跳过 QAQ。

四、关于二项式

$$\binom{n}{m}=\dfrac{n!}{m!(n-m)!}=\dfrac{n^{\underline{m}}}{m!}$$

1. 对称：$\dbinom{n}{m}=\dbinom{n}{n-m}$

2. 吸收与释放：$\dbinom{n}{m}=\dfrac{n}{m}\dbinom{n-1}{m-1}$

3. 二项式定理：

   $$(1+x)^a=\sum_{i=0}^{\infty}\binom{a}{i}x^i$$

4. 递推公式（杨辉三角）：

   $$\binom{n}{m}=\binom{n-1}{m-1}+\binom{n-1}{m}$$

5. 平行求和：

   $$\sum_{i=0}^{n}\binom{r+i}{i}=\binom{r+n+1}{n}$$

   证明：前两项之和为

   $$\binom{r}{0}+\binom{r+1}{1}=\binom{r+1}{0}+\binom{r+1}{1}=\binom{r+2}{1}$$

   然后与 $\binom{r+2}{2}$ 求和：

   $$\binom{r+2}{1}+\binom{r+2}{2}=\binom{r+3}{2}$$

   以此类推，综上得到结论。

6. 上指标求和：

   $$\sum_{i=0}^{n}\binom{i}{m}=\binom{n+1}{m+1}$$

   证明：$\binom{m}{m}=\binom{m+1}{m+1}$，与 $\binom{m+1}{m}$ 相加得到 $\binom{m+2}{m+1}$。

   剩下的递推与上个证明类似，不作赘述。

7. 范德蒙德卷积：

   $F(x)=(1+x)^{n+m}=(1+x)^n(1+x)^m$ 可以导出：

   $$f_k=\binom{n+m}{k}=\sum_{i=0}^{k}\binom{n}{i}\binom{m}{k-i}$$

8. 广义二项式系数：

   $$\binom{\alpha}{i}=\dfrac{\alpha^{\underline{i}}}{i!}$$