P4002 [清华集训2017]生成树计数
Tag：Prufer 序列 / 组合计数 / 多项式
我们使用 Prufer 序列来表示一棵树，在原图中的同一连通块中的点标为一种颜色。设第 i 个连通块的大小为 a_i，则在 i,j 两个连通块之间连一条边的贡献是 a_ia_j。设 Prufer 序列中第 i 种颜色出现的次数为 d_i，则贡献为
\frac{(n-2)!}{\prod d_i!}\prod (d_i+1)^ma_i^{d_i+1}\sum(d_i+1)^m
但这样求积与求和混在一起很不好看，考虑将其分拆为每个 d_i 的贡献：
=(n-2)!\prod a_i\sum_{j=1}^{n}\frac{\prod{a_i^{d_i}}}{\prod d_i!}(d_j+1)^{2m}\prod_{i=1,i\neq j}^{n}(d_i+1)^m
发现对于固定的 j，连通块 i 对它的贡献有两种：
\left\{\begin{matrix}
\dfrac{a_i^{d_i}}{d_i!}(d_i+1)^m & i\neq j\\
\dfrac{a_i^{d_i}}{d_i!}(d_i+1)^{2m} & i=j\\
\end{matrix}\right.
由 \sum d_i=n-2 的限制，容易想到使用 OGF，即设：
\begin{gathered}
A(x)=\sum_{k\geq 0}\frac{(k+1)^m}{k!} x^{k}\\
B(x)=\sum_{k\geq 0}\frac{(k+1)^{2m}}{k!} x^{k}
\end{gathered}
\begin{aligned}
F(x)=&\sum_{j=1}^{n}B(a_jx)\prod_{i=1,i\neq j}^n A(a_ix)\\
=&\sum_{i=1}^n \frac{B(a_ix)}{A(a_ix)}\prod_{i=1}^n A(a_ix)\\
=&\sum_{i=1}^n \frac{B(a_ix)}{A(a_ix)}\exp\sum_{i=1}^n \ln A(a_ix)
\end{aligned}
求出 [x^{n-2}]F(x) 即可得到答案。我们需要求出 \dfrac{B(x)}{A(x)} 和 \ln A(x) 后代入 a_ix 并求和，也就是对第 k 项的系数乘上 a_i^k。我们现在只需要对所有的 k 求出 \sum a_i^k 即可。虽然看似不太能做，但还是有一个奥妙重重的方法能搞定这个问题。
\begin{aligned}
G(x)=&\sum_{k\geq 0}\sum_{i} a_i^kx^k=\sum_{i}\frac{1}{1-a_ix}\\
=&\dfrac{\sum_i\prod_{j\neq i}(1-a_jx)}{\prod_i(1-a_ix)}
\end{aligned}
设分母为 Q(x)，可以分治 FFT 在 O(n\log^2 n) 时间内求出。考虑分母 P(x) 的组合意义，[x^k]P(x) 相当于 n 个物品取 k 个的一个背包，前面枚举了 j 钦定了一个物品不能被选。对于某一种选了 k 个物品方案，会有 k 个 j 不满足条件，所以 [x^k]P(x)=(n-k)[x^k]Q(x)。于是我们可以推出分子。所以这个题就两个 \log 做完了。
P4466 [国家集训队]和与积
Tag：数论分块 / 莫比乌斯反演
直接算 (a,b) 对的个数不太靠谱，考虑除掉同时除掉 d=\gcd(a,b)，得到 k_1=a/d, k_2=b/d。问题转化为求满足 k_1d+k_2d\mid k_1k_2d^2(k_1<k_2,\gcd(k_1,k_2)=1,k_2d\leq n) 的 (k_1,k_2,d) 个数。
由整除的线性性可知问题等价于 k_1+k_2\mid k_1k_2d。由
- \gcd(k,n) 在 k 固定时为积性函数
- \gcd(a,b)=gcd(a,b-a)
可知 \gcd(k_1+k_2,k_1k_2)=1。也就是说 d 需要满足的条件为 k_1+k_2\mid d 且 k_2d\leq n。容易得出可行的 d 共有 \left\lfloor\dfrac{n}{k_2(k_1+k_2)}\right\rfloor 个。那么答案为
Ans=\sum_{i=1}^{n}\sum_{j=i+1}^n[\gcd(i,j)=1]\left\lfloor\frac{n}{j(i+j)}\right\rfloor
套路地莫反一下，得
\begin{aligned}
Ans=&\sum_{d=1}^{n}\mu(d)\sum_{i=1}^{n/d}\sum_{j=i+1}^{n/d}\left\lfloor\frac{n}{d^2j(i+j)}\right\rfloor\\
=&\sum_{d=1}^{n}\mu(d)\sum_{j=2}^{n/d}\sum_{k=j+1}^{2j-1}\left\lfloor\frac{n}{d^2jk}\right\rfloor
\end{aligned}
看起来复杂度十分的不对，但实际上这个式子里变量的上界都是十分有限的。d 的实际上界为 \sqrt n，j 的实际上界为 \dfrac{\sqrt n}{d}，第三维 k 可以直接整除分块。简单积个分可以算出复杂度为 O(n^{3/4})。
P5400 [CTS2019]随机立方体
Tag：组合计数
看到「恰好 k 个极大的数」可以首先考虑二项式反演（容斥）。设 f_i 表示存在 k 个极大的数的方案数，则答案为
\sum_i(-1)^{i-k}\binom{i}{k}f_i
那么我们需要求出每个 f_i。根据定义，f_i 可以由三部分组成：
- 钦定 i 个极大数的位置
- 与极大数无关的格子任意标号
- 计算第一步中选出的格子填数的方案数
首先任意两个极大数不可能有一维坐标相等，因为这违反定义。那么有顺序地选出 i 个这样的格子的方案数共有 n^{\underline{i}}m^{\underline{i}}l^{\underline{i}} 种，每选一个格子就少一种选择。与极大数无关的格子就是任意一位坐标都与极大数不同的格子，这样的格子共有 (n-i)(m-i)(l-i) 个，标号方案数为 (nml)^{\underline{(n-i)(m-i)(l-i)}}。
最后一步比较麻烦，大概有两种方法计算：第一种是从小到大确定极大数的值，第二种是从大到小。发现最大的极大数是唯一确定的，所以从大到小计算会方便一些。当确定第 j 小的极大数时，应考虑所有只受第 j\sim n 小的极大数约束的格子，一共有 (n-j)+(m-j)+(l-j) 个，可以填的数共有 nml-(n-j)(m-j)(l-j)-1 个，贡献是这两者的一个排列数（下降幂）。把所有 1\leq j\leq i 的贡献乘起来，总方案数为：
[nml-(n-i)(m-i)(l-i)-1]!\prod_{j=1}^{i-1}\frac{1}{nml-(n-j)(m-j)(l-j)}
回代到 f 中即可求得答案。
关于求逆元，一般的做法是带 log 的，可能无法通过。但可以预处理出所有需要的逆元，见 P5431。
P4566 [CTSC2018]青蕈领主
Tag：组合计数 / 多项式
首先根据「连续」的定义，任意两个极大连续段只有包含和并列两种关系，也就是构成了一棵树。那么无解需满足 l_n\neq n 或者无法构成树（可以用栈判断）。设以 i 为根的子树的方案数为 g_i，而 i 的儿子个数为 d_i，那么把每个儿子视为一个元素，则排列后不允许存在除了整个区间以外长度 \geq 2 的连续段。设 f_i 为 i+1 个元素构成的除了整个排列以外不存在长度 \geq 2 的方案数，那么转移就是
g_i=f_{d_i}\prod_{j\in son_i}g_j
因为全都是乘法，所以答案可以写成线性相乘的形式，即
Ans=\prod_{i=1}^{n}f_{d_i}
也就是说，我们只需要求出 f 数组即可。下面给出其递归式：
f_n=\left\{\begin{matrix}
1 & n=0\\
2 & n=1\\
(n-1)f_{n-1}+\sum_{i=2}^{n-2}(n-i-1)f_if_{n-i} & n\geq 2
\end{matrix}\right.
考虑将一个长度为 n-1 的排列整体加 1 再插入 1 得到出长度为 n 的合法排列，有两种方法：
- 原排列合法，1 只需不插在 2 旁边即可；
- 原排列不合法，考虑其逆排列，发现与原排列对应，而 f_n 的意义转化为不存在不包含最大值的长度 \geq 2 的连续段的方案数。那么这个逆排列必须仅有一个不合法的连续段，这里设它的长度为 l。这个区间不能在最左边或者最右边，否则插入 1 以后还是不合法，因此共有 n-l-1 种选法。接下来将 1 与这个区间标号，方案数为 f_l；再将这个区间视为一个元素，与其它元素标号方案数为 f_{n-l}。
f_n 是可以使用分治 FFT 计算的，但因为是我 卷 我 自 己，情况会有些不同，需要注意。复杂度 O(n\log^2 n)。
P4156 [WC2016]论战捆竹竿
Tag：字符串 / 同余最短路 / DP
假设我们求出了给定字符串的所有周期长度 a_1,a_2,\cdots,a_m，那么答案就是 \sum a_ix_i 在 [0,w-n] 中能取到的值的个数。这是一个经典问题，可以用同余最短路求解，复杂度为 O(m \min a_i)，不会的话可以做一下 P3403。
但这题的 m 和 \min a_i 都可以构造到 O(n) 的级别，比如 aaa...b...aaa，b 放在靠中间的一个位置。这样复杂度就被卡到了 O(n^2)。所以我们需要发掘一下性质。
一个字符串的所有 Border 长度可以被划分成 O(\log n) 个等差数列
这句话的意思不难理解，并且一个 Border 对应了一个周期，划分成等差数列的方案也是对应的。所以怎么证明呢？
考虑设最长 Border 为 A，则所有其他 Border 也是 A 的 Border，分两种情况：
- |A|\leq n/2，此时考虑串 A 的情况即可。
- |A|>n/2，它对应的周期长度为 n-|A|，那么长度为 k(n-|A|) 的周期对应的 Border 构成了一个等差数列，并且容易证明其他 Border 的长度都 \leq n/2。于是考虑其他 Border 中最长的一个即可。
这样构造每次会将当前考虑的串长减小至少一半，最多递归 \log n 次，因此命题得证。
所以怎么用到这题上来呢，当然要对每个等差数列分别考虑。比如 x,x+d,\cdots, x+(l-1)d 这个等差数列，我们在模 x 意义下跑同余最短路。发现实际上这就是个模意义下多重背包的问题，最多选 l-1 个物品，这一类的物品体积为 d，选出 k 个的代价为 x+(k-1)d。可以把环拆开看，用单调队列优化即可。
还有一个问题就是不同「物品」的模数都是不同的，如何在不同模数下转换。假设原模数为 lst，当前模数为 cur，则显然 f_i 是可以更新 f_{f_i\bmod cur} 的，这可以直接处理出来。但 f_i 在模 cur 意义下还可以更新 f_{(i+lst)\bmod cur}，因此还需要跑一次环上的完全背包（没有 l 的限制），就不需要单调队列了。复杂度 O(Tn\log n)。
冷滟泽的个人博客