组合
模数默认\(998244353\)。
数学
特征方程
求解 \(F_n=a F_{n-1}+b F_{n-2}\)。
假设这是一个公比为 \(q\) 的等比数列，那么 \(q^2 F_{n-2}-a q F_{n-2}-b F_{n-2}=0\)。
解 \(q^2-aq-b=0\) 可以得到两个根 \(q_0,q_1\)。
不难发现，对于任意 \(F_n=u q_0^n+v q_1^n\) 均满足递推式。
只需要两个点值解出方程即可。
常系数齐次线性递推
对于数列 \(F\) 和常数列 \(C\)，满足 \(n\ge k\) 时 \(\displaystyle \sum_{i=0}^{k}C_i F_{n-i}=0\) 则称 \(F\) 满足 ( \(k\) 阶 ) 线性常系数递推关系。
令 \(F(x)\) 为 \(F\) 的生成函数，构造 \(\displaystyle F_t(x)=C_tx^t \left(F(x)-\sum_{i=0}^{k-t-1}F_ix^i \right)\)。
可以发现 \([x^n]F_t(x)=[n\ge k]C_t F_{n-t}\) 。
又因为 \(\displaystyle [n\ge k]\sum_{i=0}^{k}C_i F_{n-i}=0\) 能得到 \(\displaystyle\sum_{t=0}^{k}F_t(x)=0\)，即 \(\displaystyle \sum_{t=0}^{k} C_tx^t \left(F(x)-\sum_{i=0}^{k-t-1}F_ix^i \right)=0\)。
整理： \(\displaystyle \sum_{t=0}^{k} C_t x^t F(x)= \sum_{t=0}^{k-1}C_t x^t\sum_{i=0}^{k-t-1}F_ix^i=\sum_{t=0}^{k-1}x^t\sum_{i=0}^{t}C_{t-i}F_i\)。
可以发现，左边有明显的 \(C\) 的生成函数 \(C(x)\)，右边是一个 \(k-1\) 次多项式 \(P(x)\)。
那么 \(F(x)=\dfrac{P(x)}{C(x)}\) 。
分式分解
上一个的逆变换，咕咕咕。
卡特兰数
定义：\(n\) 对括号的合法序列数，记为 \(C\)，\(C_0=1\)。
有一个简单递推式：\(\displaystyle C_{n+1}=\sum_{i=0}^n C_i C_{n-i}\)。
组合理解 : 枚举第一对括号里面装了多少东西，其内外各为完整的合法序列。
这个式子看起来非常像卷积，我们令其自卷：\(\displaystyle C^2_n=\sum_{i=0}^n C_i C_{n-i}=C_{n+1}\)。
令卡特兰数生成函数为 \(C(x)\)。
不难得到 \(C_{n+1}\) 处的幂级数为 \(\dfrac{C(x)-1}x\)。
那么 \(C^2(x)=\dfrac{C(x)-1}x\)。解得 \(C(x)=\dfrac{1\pm\sqrt{1-4x}}{2x}\)。
根据 \(x\to 0\) 时的极限，\(C(x)=\dfrac{1+\sqrt{1-4x}}{2x}\) 显然不合法。
所以可以根据广义二项式定理得到 \(C(x)=\dfrac{1-\sum_i\binom{\frac 12} i (-4)^i x^i}{2x}\)。
\[\begin{aligned} C_{i}&=-\frac {\binom{\frac 12}{i+1}(-4)^{i+1}}2\\ &=-\frac {\prod\limits_{j=0}^{i}\frac{1-2 j}2(-4)^{i+1}}{2(i+1)!}\\ &=-\frac {\prod\limits_{j=0}^{i}(1-2 j)(-4)^{i+1}}{2^{i+2}}\\ &=-\frac {(-1)^i\prod\limits_{j=1}^{i}(2 j-1)(-4)^{i+1}}{2^{i+2}}\\ &=\frac {(2i-1)!4^{i+1}}{2^{2i+1}(i-1)!(i+1)!}=\frac{2(2i-1)!}{(i-1)!(i+1)!}=\frac{\binom{2i}i}{i+1}\\ \end{aligned} \]题
Luogu 4931 [MtOI2018]情侣？给我烧了！（加强版）
\(n\) 对情侣，坐 \(n\) 行 \(2\) 列个位置，问有多少方案恰好有 \(k\) 对情侣坐在同一行。
多次询问。\(0\le k\le n\le 5\times 10^6,1\le T\le 2\times 10^5\)。
题解：
二项式反演。令 \(G(x)\) 为钦定 \(k\) 对的方案数，\(H(x)\) 为恰好 \(k\) 对的方案数。
不难发现 \(\displaystyle G(i)=\binom n i^2 i! 2^i(2n-2 i)!\)（选哪些对，选哪些行，对之间可以互换，对内部可以互换，剩下随便放）。
\[\begin{aligned} H(x)&=\sum_{i=x}^n (-1)^{i-x}\binom i x G(i)\\ &=\sum_{i=x}^n (-1)^{i-x}\binom i x \binom n i^2 i! 2^i(2n-2 i)!\\ &=\sum_{i=x}^n (-1)^{i-x}\frac{n!n!}{x!(i-x)!(n-i)!(n-i)!}2^i(2n-2 i)!\\ &=\frac{(n!)^2}{x!}\sum_{i=x}^n \frac{(-1)^{i-x}}{(i-x)!}2^i\binom{2n-2i}{n-i}\\ &=\frac{(n!)^2 2^x}{x!}\sum_{i=x}^n \frac{(-2)^{i-x}}{(i-x)!}\binom{2n-2i}{n-i}\\ &=\frac{(n!)^2 2^x}{x!}\sum_{i=0}^{n-x} \frac{(-2)^{i}}{i!}\binom{2n-2i-2x}{n-i-x}\\ &=\frac{(n!)^2 2^x}{x!}\sum_{i=0}^{n-x} \frac{(-2)^{i}}{i!}\binom{2n-2i-2x}{n-i-x}\\ \end{aligned} \]右边是卷积形式，常数小直接过，但是没必要。
先不管左边的常数，设右边的生成函数为 \(F(x)\)，记为数列 \(F\)。
令生成函数 \(\displaystyle F_1(x)=\sum_i \frac{(-2)^i}{i!} x^i=e^{-2x}\)，\(\displaystyle F_2(x)=\sum_i \binom{2 i}i x^i\) ，那么 \(F(x)=F_1(x)F_2(x)\)。
\(F_2\) 有点困难，需要注意到 \(\displaystyle \binom{2i}i=\binom{i-\frac 12}{i}4^i=\binom{-\frac 12}i(-4)^i\)。
然后使用广义二项式定理：\(F_2(x)=\displaystyle \sum_i \binom{-\frac 12}i(-4)^i x^i=(1-4 x)^{-\frac12}\)。
所以 \(F(x)=\dfrac{e^{-2x}}{\sqrt{1-4x}}\)。
考虑经典的求导：
\[\begin{aligned} F'(x)&=\frac{8x}{1-4x}F(x)\\ F'(x)&=4xF'(x)+8xF(x)\\ [x^n]F'(x)&=4[x^{n-1}]F'(x)+8F_{n-1}\\ (n+1)F_{n+1}&=4nF_n+8F_{n-1} \end{aligned} \]可以递推了。
初步
组合对象
组合对象指满足某一性质的树、图、串等可数的对象。组合对象组成的集合成为组合类。
对于组合类 \(\mathcal A\) ，其中每个对象 \(a\in\mathcal A\) 都被定义了一个 “大小” \(|a|\)，可能代表节点个数，串长等。
将所有大小为 \(n\) 的组合对象记作 \(\mathcal A_n\)。
定义计数序列 \(A_n=|\mathcal A_n|\) ，即大小为 \(n\) 的组合对象的总数目。
我们的任务通常是求出 \(A_n\) 的数值。
笛卡尔积
称 \(\{(a_1,\dots,a_n)|a_i\in A_i,i\in[1,n]\}\) 为集合 \(A_{1\sim n}\) 的笛卡尔积。
记作 \(A_1\times A_2\times \dots\times A_{n}\)。也就是从每个集合中各取一个元素形成有序多元组的集合。
也就是从每个集合中各取一个元素形成有序多元组的集合。
对于两个组合对象 \(a,b\) 的组合 \((a,b)\) ，定义 \(|(a,b)|=|a|+|b|\)。
这是非常自然的，比如两个长度为 \(a,b\) 的串接起来就得到了一个长度为 \(a+b\) 的串。
OGF
普通生成函数（ordinary generating function）
设有数列 \(F\)，那么 \(F\) 的生成函数为 \(\displaystyle F(x)=\sum_{i=0}F_i x^i\)。
\[[x^n](F\times G)=\sum_{i+j=n}F_i G_{j} \]经典 OGF 及封闭形式
-
\(\forall i\ge 0,F_i=1\)：\(F(x)=\displaystyle\frac{1}{1-x}\)
\[\begin{aligned} F(x)&=\sum_{i\ge 0}x^i \\ xF(x)&=\displaystyle \sum_{i\ge 1}x^i\\ xF(x)&=F(x)-1 \end{aligned} \] -
\(F_0=0,\forall i\ge 0,F_i=1\)：\(F(x)=\displaystyle\frac{x}{1-x}\)
\[\begin{aligned} F(x)&=\sum_{i\ge 1}x^i \\ xF(x)&=\displaystyle \sum_{i\ge 2}x^i\\ xF(x)&=F(x)-x \end{aligned} \] -
\(\forall i\ge 0,F_i=a^i\)：\(F(x)=\displaystyle\frac{1}{1-ax}\)
\[\begin{aligned} F(x)&=\sum_{i\ge 0}a^ix^i \\ axF(x)&=\displaystyle \sum_{i\ge 1}a^ix^i\\ axF(x)&=F(x)-1 \end{aligned} \] -
\(\forall i\ge 0,F_i=[k|i]\)（ \(|\) 是整除）：\(F(x)=\dfrac{1}{1-x^k}\)
\[\begin{aligned} F(x)&=\sum_{i\ge 0}x^{ik} \\ x^kF(x)&=\displaystyle \sum_{i\ge 1}x^{ik}\\ x^kF(x)&=F(x)-1 \end{aligned} \] -
\(\forall i\ge 0,F_i=[k|i]a^{\frac i k}\)（ \(|\) 是整除）：\(F(x)=\dfrac{1}{1-ax^k}\)
\[\begin{aligned} F(x)&=\sum_{i\ge 0}a^ix^{ik} \\ ax^kF(x)&=\displaystyle \sum_{i\ge 1}x^{ik}\\ ax^kF(x)&=F(x)-1 \end{aligned} \] -
\(F_0=0,\forall i\ge 1,F_i=\dfrac 1 i\)：\(F(x)=-\ln(1-x)\)
\[\begin{aligned} F(x)&=\sum_{i\ge 1}\frac {x^i}i \\ F'(x)&=\sum_{i\ge 0}x^i=\frac 1{1-x} \\ F(x)&=\int\frac{\mathrm dx}{1-x}=-\ln(1-x) \end{aligned} \] -
\(\forall i\ge 0,F_i=\dfrac 1{i!}\)：\(F(x)=e^x\)
\[\begin{aligned} F(x)&=\sum_{i\ge 1}\frac {x^i}{i!} =e^x\\ \end{aligned} \]（泰勒展开）
-
\(\forall i\ge 0,F_i=i+1\)：\(F(x)=\dfrac 1{(1-x)^2}\)
\[\begin{aligned} F(x)&=\sum_{i\ge 0}(i+1){x^i} \\ \int F(x)\mathrm dx&=\int \sum_{i\ge 1}ix^{i-1}\mathrm dx=\sum_{i\ge 0}x^i =\frac 1{1-x}\\ F(x)&=\left(\frac1{1-x}\right)'=\frac1{(1-x)^2} \end{aligned} \] -
\(\forall i\ge 0,F_i=\displaystyle\binom{n}{i}\)：\(F(x)=(1+x)^n\)
\[\begin{aligned} F(x)&=\sum_{i\ge 0}\binom{n}{i}{x^i} =(1+x)^n\\ \end{aligned} \]（二项式定理）
-
\(\forall i\ge 0,F_i=\displaystyle\binom{n+i}{i}\)：\(F(x)=\dfrac{1}{(1-x)^{n+1}}\)
归纳，\(n=0\) 显然。当 \(n\ge 1\) 时：
\[\begin{aligned} \dfrac{1}{(1-x)^{n+1}}&=\frac{1}{(1-x)^n}\frac 1{1-x}\\ &=\left(\sum_{i\ge0}\binom{n-1+i}{i}x^i\right)\left(\sum_{i\ge0}x^i\right)\\ &=\sum_{i\ge0}x^i\sum_{j=0}^i\binom{n-1+j}{j}\\ &=\sum_{i\ge0}\binom{n+i}{i}x^i \end{aligned} \]
题
\(1\). 设某种号码由小写英文字母和数字组成，且所有数字都出现在字母之后。允许没有英文或数字。求长度为 \(n\) 的号码个数。
题解：
长为 \(n\) 的纯字母串的生成函数为 \(F(n)=\dfrac{1}{1-26x}\)，纯数字串的生成函数为 \(G(n)=\dfrac 1 {1-10x}\)。
枚举字母个数可以得到答案 \(S_n=\displaystyle \sum_{i+j=n} F_i G_{j}\) 。所以 \(S(x)=F(x)G(x)=\dfrac{1}{(1-10x)(1-26x)}\)。
$2. $ 有若干种颜色互不相同的骨牌，其中长度为 \(i\) 的骨牌有 \(a_i\) 种。每种颜色的骨牌都可以无限次使用，求不重叠地铺到恰好长度 \(n\) 的方案数。
令 \(A(x)\) 为 \(a\) 的生成函数。
枚举数量 \(i\)，答案的生成函数即为 \(\displaystyle \sum_{i=0}A(i)^k=\frac 1{1-A(x)}\)。
求逆即可。
\(3.\) [国家集训队2011答辩]整数的lqp拆分
给定 \(n\)，求 \(\displaystyle\sum_{m>0,a_i>0(i\in[1,m]),\sum\limits_{i=1}^ma_i=n}\prod_{i=1}^m F_{a_i}\)，其中 \(F\) 是斐波那契数列。
\(1\le n\le 10^{10000}\)。
不难发现，本题可以看做上一题 \(a_i=F_i\) 的情况。
又因为 \(F(x)=xF(x)+x^2F(x)-F_0x+F_1x\Rightarrow F(x)=\dfrac{x}{1-x-x^2}\)。
那么，答案的生成函数为 \(\dfrac{1}{1-\frac{x}{1-x-x^2}}=\dfrac{1-x-x^2}{1-2x-x^2}=1-\dfrac{x}{x^2+2x-1}\)。
由于 \(n\ge 1\)，前面的这个 \(1\) 没有用。
分式分解，令 \(x_1,x_2\) 为 \(x^2+2x-1=0\) 的两根，即：
\[\begin{aligned} &=-\dfrac{x}{x^2+2x-1}\\ &=\frac{x}{x_2-x_1}\left(\frac1{x-x_1}-\frac1{x-x_2}\right)\\ &=\frac{x}{x_2-x_1}\left(\frac1{\frac{x}{x_1}-1}\frac1{x_1}-\frac1{\frac{x}{x_2}-1}\frac1{x_2}\right)\\ &=\frac{x}{x_2-x_1}\left(-\frac1{x_1}\sum_{i\ge 0} \frac{x^i}{x_1^i}+\frac1{x_2}\sum_{i\ge 0} \frac{x^i}{x_2^i}\right)\\ &=\frac{1}{x_2-x_1}\left(\sum_{i\ge 1} \frac{x^i}{x_2^i}-\sum_{i\ge 1} \frac{x^i}{x_1^i}\right)\\ \end{aligned} \]第 \(n\) 项的系数即为 \(\displaystyle \frac1{x_2-x_1}\left(\frac1{x_2^n}-\frac1{x_1^n}\right)=\frac{1}{2\sqrt2}((1+\sqrt2)^n+(1-\sqrt2)^n)\)。
可以处理出二次剩余，然后直接算。
$4. $ Codeforces 438 E
给定不可重集合 \(C\)，对于 \(j\in[1,m]\) 求有多少棵带点权的不同构二叉树满足：令 \(i\) 的点权为 \(a_i\)，\(a_i\in C,\sum_ia_i=j\)。
二叉树区分左右儿子。\(1\le n,m,c_i\le 10^5\)。
令 \(f_i\) 表示权值为 \(i\) 的二叉树的方案数，可以得到：
\[f_n=\sum_{i=0}^n\sum_{j=0}^{n-i}[i\in C]f_jf_{n-i-j} \]令 \(F(x)\) 为 \(f\) 的生成函数，\(G(x)=\sum\limits_{i\ge0}[i\in C]x^i\)。
那么不难看出 \(F(x)=F^2(x)G(x)+1\)。
解得 \(F(x)=\dfrac{1\pm\sqrt{1-4G(x)}}{2G(x)}\)，利用 \(x\to 0\) 时的判别，发现取 \(+\) 时显然错误。
这里 \(2G(0)=0\) 不能求逆。
那么
\[\begin{aligned} F(x)&=\dfrac{1-\sqrt{1-4G(x)}}{2G(x)}\\ &=\dfrac{(1-\sqrt{1-4G(x)})(1+\sqrt{1-4G(x)})}{2G(x)(1+\sqrt{1-4G(x)})}\\ &=\dfrac{4G(x)}{2G(x)(1+\sqrt{1-4G(x)})}=\frac{2}{1+\sqrt{1-4G(x)}} \end{aligned} \]其实不是特别严谨，因为 \(G\) 不能求逆，严谨一点只要每一步把 \(G\) 带上即可，过程几乎相同，懒了。
\(n\) 种大小为 \(v_i\) 的无限多的商品，对于 \(s\in[1,m]\) 求出商品恰好装 \(s\) 的方案数。
\(1\le n\le 10^5,1\le v_i\le m\le 10^5\)。
题解：
一个物品的生成函数 \(\displaystyle V_i(x)=\sum_{j\ge 1}x^{jv_i}=\frac{1}{1-x^{v_i}}\)，答案的生成函数就是把它们都乘起来。
由于是分数，所以我们把求逆放最后，先求卷积。
有一个技巧：取 \(\ln\) 之后，你就可以直接做加法了，最后 \(\exp\) 一下。
所以
\[\begin{aligned} \ln(1-x^{v_i})&=\int \frac{-v_ix^{v_i-1}}{1-x^{v_i}}\mathrm d x \\&=-v_i\int\frac{x^{v_i-1}}{1-x^{v_i}}\mathrm dx \\&=-v_i\int\sum_{j\ge 1}x^{jv_i-1}\mathrm dx \\&=-v_i\sum_{j\ge 1}\frac{x^{jv_i}}{jv_i} \\&=-\sum_{j\ge 1}\frac{x^{jv_i}}{j} \end{aligned} \]这样可以用埃式筛预处理。