简单数数杂题（几乎无 poly，可放心食用）
Aleph1022
·
·
个人记录
难度大致以 NOIP 为参考（比如 T4 可能是没有上限的（雾）），以达到我的叙述做法的复杂度为准。
写作目的可能是休闲、简单收集，或者某种意义上是科普（所以会有一些典题）
会尽量减少 poly 成分。
欢迎投稿题目（雾）
目前需要完善的东西：
- 有关 AGC058D 和 CF1093F 的容斥系数。
「BJOI2017」机动训练
难度：T2。
考虑将平方看做组合意义：两个人走地形序列相同的路径的方案数。
对于方向的问题，可以将方向分为四类：左、上、左上；右、上、右上；左、下、左下；右、下、右下。
那么一条路径一定是一直走同类方向的。
然而一直向左、上、右、下的路径会被算重，于是再减去即可。
使用记搜实现，否则较难确定转移顺序。
「ZJOI2019」麻将
难度：T3.5。
考虑 DP 判定，设 f(i,0/1,j,k) 表示考虑 1,\dots,i 的牌，是否有雀头，剩下 j 个 (i-1,i) 和 k 个 i 的情况下能得到的最大面子数。
显然，可以令 j, k < 3。
将 DP 删去第一维，建出自动机。笔者所得到的状态数为 2092。
计算答案，考虑经典的 E(X) = \sum_{k\ge 0} P(X>k)。
于是关键就是算出摸了 k 张牌都不和牌的方案数。DP 即可。
「JSOI2019」神经网络
难度：T2.5。
对 i,j 算出将第 i 棵树划分为 j 条链的方案数。注意到长度大于 1 的链应当有正反两种方案。
然后背包计算，容斥一下即可。
「PKUSC2018」最大前缀和
难度：T3。
考虑枚举构成最大前缀和的数，这样就需要计算 f(S) 为 S 的排列，严格最大前缀和为 \sum_{i\in S} a_i 的方案数，和 g(S) 为 S 的排列，前缀和均 \le 0 的方案数。
## 「CF1093F」Vasya and Array
难度：T3。
大力 DP，设 $f(i,j)$ 表示前 $i$ 个数，第 $i$ 个位置填 $j$ 的合法方案数。容易 $O(nk)$ 转移。
让我们来了解一下 $O(n)$ 做法。
一个考虑是优化上述 DP，也可以做到同复杂度。略去不表。
考虑容斥，钦定一些同色段，那么长度为 $len$ 的倍数的同色段会带有容斥系数 $-1$，长度模 $len$ 余 $1$ 的同色段会带有容斥系数 $1$，其余长度不应被计算。
容易验证这样贡献就可以正确组合出答案。
那么 DP 就行了。对于每个右端点，有一个区间内的左端点与之构成同色段的方案数是 $k$，还有一个区间方案数是 $1$。前缀和优化即可。
## 「COCI 2019.03」Mobitel
难度：T2。
记状态 $f(i,j,k)$ 表示走到 $(i,j)$，当前权值至少乘 $k$ 后不小于 $n$ 的方案数。
可知不同的 $k$ 只有 $O(\sqrt n)$ 个，时间复杂度 $O(rs\sqrt n)$。
## 「CTS2019」氪金手游
难度：T3。
假设图为外向树，且我们知道了 $W_i$，那么题目将类似于拓扑序计数。
这是因为，这样的模型可以由从所有卡中随机转化为从还没有得到的卡中随机，可以验证其概率是不变的。
我们接下来解决获得一个拓扑序的概率：记 $S_u$ 为 $u$ 子树内的 $W_i$ 之和。那么 $u$ 在子树内第一个被随机出来的概率就是 $\frac{W_u}{S_u}$。
因此答案为 $\prod_{u=1}^n \frac{W_u}{S_u}$。
假设图为外向树，但我们不知道 $W_i$，DP 即可。设 $f(u,s)$ 表示 $u$ 的子树内，$S_u=s$ 的所有方案的 $W_i/S_i$ 的积之和。
最后一个问题是图不一定是外向树。我们考虑将大于号转化为无限制减去小于号，无限制就相当于断了一条边，小于号相当于建了一条反向边，这样就转化为了外向树的问题。
时间复杂度 $O(n^2)$。
## 「PKUWC2018」随机游走
难度：T2.5。
考虑 min-max 容斥，那么我们先对每个点集计算最早访问到该点集内的点的期望时间。然后使用高维前缀和即可将子集求和。
这个问题是典型的树上游走问题，考虑 DP，设 $f(u)$ 表示从结点 $u$ 出发走到 $S$ 中任意点的期望步数。
那么有
$$
f(u) = \frac 1{\deg_u} \left(f(\mathrm{fa}_u) + \sum_{v \in \mathrm{son}_u} f(v)\right) + 1
$$
看起来转移有环，但是实际上在树上可以用待定系数解决这样一个 DP。
设
$$
f(u) = k_u f(\mathrm{fa}_u) + b_u
$$
那么有
$$
\begin{aligned}
f(u)
&= \frac 1{\deg_u} \left(f(\mathrm{fa}_u) + \sum_{v \in \mathrm{son}_u} f(v)\right) + 1 \\
&= \frac 1{\deg_u} \left(f(\mathrm{fa}_u) + \sum_{v \in \mathrm{son}_u} (k_v f(u) + b_v)\right) + 1 \\
\deg_u f(u)
&= f(\mathrm{fa}_u) + \sum_{v \in \mathrm{son}_u} (k_v f(u) + b_v) + \deg_u \\
&= f(\mathrm{fa}_u) + f(u) \sum_{v \in \mathrm{son}_u} k_v + \sum_{v \in \mathrm{son}_u} b_v + \deg_u \\
\left(\deg_u - \sum_{v \in \mathrm{son}_u} k_v\right) f(u)
&= f(\mathrm{fa}_u) + \sum_{v \in \mathrm{son}_u} b_v + \deg_u \\
f(u)
&= \frac 1{\deg_u - \sum_{v \in \mathrm{son}_u} k_v} \cdot f(\mathrm{fa}_u) + \frac{\deg_u + \sum_{v \in \mathrm{son}_u} b_v}{\deg_u - \sum_{v \in \mathrm{son}_u} k_v}
\end{aligned}
$$
于是这样枚举所有 $S$ DP 即可，复杂度 $O(n 2^n \log P)$，其中 $P = 998244353$。
## 「AGC005D」~K Perm Counting
难度：T2.5。
连接 $i$ 和 $i\pm k$ 可以得到一张由链构成的图。
考虑钦定 $i$ 条边在排列中相邻，那么我们知道其恰好构成 $n-i$ 个连通块，故容易容斥。
背包计算即可，每条链上的答案可以用隔板法算出。
## 「ABC221H」Count Multiset
难度：T2.5。
我们把多重集里的数降序，然后画成直方图。
转化为上边缘的一条路径。
其满足：
- 从 $x=0$ 上的某处出发；
- 走到 $x=k$ 上的某处；
- 每一步可以往右或者往下；
- 下方面积为 $n$；
- 最多连续向右走 $m$ 步。
把这个图像向左旋转 $90^\circ$，得到一条路径，满足：
- 从 $y=0$ 上的某处出发；
- 走到 $y=k$ 上的某处；
- 每一步可以往右或者往上；
- 下方面积为 $n$；
- 最多连续向上走 $m$ 步。
DP。设 $f(n,h)$ 表示面积为 $n$，高度为 $h$ 的方案数。
枚举上一列的高度即可转移：
$$
f(n,h) = \sum_{1\le i\le h, h-i\le m} f(n-h,i)
$$
前缀和优化即可。
也存在代数推导。
## 「CF1515E」Phoenix and Computers
难度：T2.5。
从左往右 DP，记状态 $f(i,j)$ 表示目前有 $i$ 台电脑，手动开的电脑形成 $j$ 个连续段的方案数。
转移考虑扩展一段或新增一段，即 $f(i,j) = 2j \cdot f(i-1,j) + j \cdot f(i-2,j-1)$。
也可以用连续段 DP 模拟开电脑的过程。
也存在 GF 做法，经过化简，与上述做法有本质相同的计算式。
~~通过拉格朗日反演和牛顿迭代，在 NTT 模数下也可以优化到 $O(n\log n)$~~
## 「JOISC 2020 Day2」遗迹
难度：T4。
考虑一个判定算法，从大到小枚举编号，记录最终哪些高度的石柱编号已经确定了，那么当前石柱的最终高度就是不高于初始高度的最大的还没有确定的高度。
设 $f(i,j)$ 表示 $i,\dots,2N$ 的石柱的最终高度钦定有极大前缀 $1,\dots,j$。
考虑转移：
- 若 $i \in A$，则必然有 $1\le h_i \le j$，否则可以取到 $j+1$。
似乎还是不太好做，考虑区分同一种高度的两根石柱，则方案数就是 $j$ 减去 $i,\dots,2N$ 中没有留到最后的个数。
- 若 $i \notin A$，若其最终高度 $>j+1$，则**延迟计算其贡献**（在扩展前缀时计算）；
否则，枚举前缀扩展了 $k$，则 $h_i$ 可以取 $k+1$ 种值，然后选取 $j+2,\dots,j+k$ 共 $k-1$ 种最终高度的出现位置，然后乘一个系数 $g_{k-1}$。
$g_k$ 是一个子问题：填入 $1,\dots,k$ 的初始高度，使得最终高度恰为 $1,\dots,k$ 的方案数。
根据前面的判定算法，条件就是对每个 $1 \le i \le k$ 都满足不大于 $i$ 的元素个数不超过 $i$。
设 $g(i,j)$ 表示在 $j$ 个位置填入 $1,\dots,i$ 的元素的方案数，则
$$
g(i,j) = g(i-1,j) + 2j \cdot g(i-1,j-1) + j(j-1) \cdot g(i-1,j-2)
$$
则 $g_k = g(k, k)$。
## 「CF1608F」MEX counting
难度：T3。
设 $f(i,j,t)$ 表示考虑 $a_{1,\dots,i}$，$\operatorname{mex} = j$，还有 $t$ 种值被延迟确定的方案数。
转移：
- $a_i < j$，$f(i,j,t) \gets f(i,j,t) + j \cdot f(i-1,j,t)$。
- $a_i > j$，$f(i,j,t) \gets f(i,j,t) + t \cdot f(i-1,j,t) + f(i-1,j,t-1)$。
- $a_i = j$，枚举扩展的长度 $c$，$f(i,j+c,t-c+1) \gets f(i,j+c,t-c+1) + t^{\underline{c-1}} \cdot f(i-1,j,t)$。
显然 $j$ 只有 $O(k)$ 种取值。
对于第三种转移，注意到 $(j+c)+(t-c+1) = j+t+1$ 是定值，从而容易在坐标变换后使用前缀和优化。
## 「AGC058D」Yet Another ABC String
难度：T3。
设容斥系数是 $G(x)$，我们知道
$$
\begin{aligned}
\frac1{1-G(x)} &= 1 + x + x^2 = \frac{1-x^3}{1-x} \\
G(x) &= \frac{x-x^3}{1-x^3}
\end{aligned}
$$
考虑组合容斥单位，借助三元 GF，那么这个东西就变成了
$$
\frac{x+y+z-3xyz}{1-xyz}
$$
组合，就有
$$
\begin{aligned}
F(x,y,z)
&= \frac1{1-\frac{x+y+z-3xyz}{1-xyz}} \\
&= \frac{1-xyz}{1-x-y-z+2xyz} \\
&= \frac1{1-x-y-z} \frac{1-xyz}{1-\frac{-2xyz}{1-x-y-z}} \\
[x^Ay^Bz^C] F(x,y,z)
&= [x^A y^B z^C] \sum_{k\ge 0} \frac{(1-xyz)(-2xyz)^k}{(1-x-y-z)^{k+1}} \\
&= \sum_{k\ge 0} (-2)^k \left[\binom{A+B+C-2k}{k, A-k, B-k, C-k} - \binom{A+B+C-2k-3}{k, A-k-1, B-k-1, C-k-1}\right] \\
\end{aligned}
$$
这个最终式子的一个组合意义由 [gyh20 的做法](https://www.luogu.com.cn/blog/gyh20/agc058d)给出。
## 洛谷 7278. 纯洁憧憬
难度：T4（假设不知道析合树）。
顺便重构一下题解，去掉析合树内容。
令连续段表示值域与位置都连续的区间。先取补集，计算所有非平凡连续段长度都不超过 $k$ 的排列数。
直观来看，假设我们能每次将当前所有非平凡连续段（长度不为 $1,n$ 的连续段）分别缩成一个数，那么反复执行以上操作，最后会得到一个不存在非平凡连续段的排列。
那么对于上面的计数，我们其实只关心第一次缩的连续段是否都不超过 $k$。
假设我们算出了没有非平凡连续段的排列个数 $f_i$（这也被称作单排列），似乎只需要背包将长度不超过 $k$ 的排列组合起来即可。
然而其实这不太正确。如若最后得到排列 $[1,2]$ 或 $[2,1]$，那么我们缩连续段的方式并不唯一。这实际上取决于当前排列能切成多少个值域刚好是顺序或逆序的连续段。
不妨考虑得到 $[1,2]$ 的排列，设其一个合法的段的方案数为 $g_i$，则取补集可以递推 $g_i = i! - \sum_{j=1}^{i-1} g_j (i-j)!$。
然后这部分贡献是 $2\sum_{i\ge n-k} \sum_{j\ge n-k} g_i g_j (n-i-j)!$。
考虑计算 $f_i$。直接算是很困难的，我们不妨利用全体排列的结构进行计算。只需要用 $i!$ 减去得到 $[1,2],[2,1]$ 的排列个数以及缩出的段数 $<i$ 的方案数。
前者我们已经算出来了，后者不难想到设段数及总长暴力 DP 计算。
最后再做一次类似的 DP 即可。
时间复杂度 $O(n^3)$。
~~似乎 $O(n\log^2 n)$ 的版本已经出出来了~~
## 「USACO 2020.12 Platinum」Spaceship
难度：T2.5。
为了方便叙述还是使用了一些代数记号。组合意义应该也是容易理解的。
令邻接矩阵是 $\mathbf G$，所有元素 $\le k$ 的满足条件的序列的 GF 为 $F_k(z)$。
那么如果不考虑 $b_s,s,b_t,t$，答案无非就是 $\mathbf G^{-1} F_k(\mathbf G)$。
不难发现计数 $F_k(z)$ 可以拆出最大值，即
$$
F_k(z) = z\sum\limits_{i=1}^k (1+F_{i-1}(z))^2
$$
那么考虑维护出所有 $F_k(\mathbf G)$，自然就是
$$
F_k(\mathbf G) = \mathbf G\sum\limits_{i=1}^k (1+F_{i-1}(\mathbf G))^2
$$
注意到平方只要计算 $k$ 次，那么计算所有 $F_k(\mathbf G)$ 的总复杂度就是 $O(k^2n^2+kn^3)$。
令 $\mathbf v_s$ 是行向量 $([i=s])_{i=1}^n$。
令 $F_{b_s,0,k}(z),F_{0,b_t,k}(z),F_{b_s,b_t,k}(z)$ 分别是限定了序列首尾的 GF，那么有
$$
\begin{aligned}
F_{b_s,0,k}(z) &= z \sum\limits_{i=1}^k \left[F_{b_s,0,i-1}(z)(1+F_{i-1}(z))+[i=b_s](1+F_{i-1}(z))\right] \\
F_{0,b_t,k}(z) &= z \sum\limits_{i=1}^k \left[F_{0,b_t,i-1}(z)(1+F_{i-1}(z))+[i=b_t](1+F_{i-1}(z))\right] \\
F_{b_s,b_t,k}(z) &= z \sum\limits_{i=1}^k \left[F_{b_s,0,i-1}(z)F_{0,b_t,i-1}(z)+[i=b_s]F_{0,b_t,i-1}(z)+[i=b_t]F_{b_s,0,i-1}(z)+[i=b_s=b_t]\right]
\end{aligned}
$$
不妨直接维护出所有 $\mathbf v_s F_{b_s,0,k}(\mathbf G),F_{0,b_t,k}(\mathbf G) \mathbf v_t^T,\mathbf v_s \mathbf G^{-1} F_{b_s,b_t,k}(\mathbf G) \mathbf v_t^T$。
根据递推式，维护前两者可以做到 $O(kn^2)$（向量乘矩阵），维护第三者可以做到 $O(kn)$（向量乘向量）。
注意到 $\mathbf G$ 可能没有逆，但是只需要注意到递推时必然会多贡献一个 $\mathbf G$，去掉即可。
时间复杂度 $O(k^2n^2+kn^3+qkn^2)$。
## 「CF917D」Stranger Trees
难度：T2.5。
典题。
> 引理.
> 对于 $k$ 个大小为 $a_1, a_2, \dots, a_k$ $(\sum_i a_i=n)$ 的连通块，连接恰好 $k-1$ 条边使得图连通的方案数为
> $$n^{k-2} \prod_{i=1}^k a_i$$
>
> 可以通过枚举 Prufer 序列推得该结论。
进行二项式反演，计算钦定有 $k$ 条边不重复的方案数。注意到 $a_i$ 的积可以通过组合意义变成选择一个点的方案数。
于是设 $f(u,i,0/1)$ 表示 $u$ 的子树内，断了 $i$ 条边，当前连通块内是否选了点的方案数即可。
时间复杂度 $O(n^2)$。
## 洛谷 8558. 黑暗（Darkness）
难度：T2。
假设走到了 $(x,y,0)$，其余三者对称，则答案为
$$
\begin{aligned}
&\quad\; \sum_{x \ge 1} \sum_{y \ge 1} (x+y)^k 3^{-(A+B+C-x-y)}\binom{A+B+C-x-y}{A-x,B-y,C} \\
&= \sum_{s \ge 2} s^k 3^{s-A-B-C} \binom{A+B+C-s}C \sum_{x\ge 1}\binom{A+B-s}{A-x}
\end{aligned}
$$
枚举 $s$，后者是上指标为 $A+B-s$ 的组合数的一个区间和，容易递推。
## LibreOJ 6677. EntropyIncreaser 与菱形计数
难度：T3（假设杨表不超纲）。
瞪一瞪题中的图，就可以发现组合意义：$a\times b$ 的矩阵 $h_{i,j}$，每个位置填入不超过 $c$ 的自然数，使得 $h_{i,j} \ge h_{i+1,j}, h_{i,j} \ge h_{i,j+1}$。
不难双射到形状为 $a\times b$ 的矩阵，元素范围为 $1,\dots,a+c$ 的半标准杨表，那么我们直接使用钩长公式：
$$
\prod_{i=1}^a \prod_{j=1}^b \frac{a+c+j-i}{a+b-i-j+1} = \prod_{i=1}^a \frac{(a+b+c-i)!(a-i)!}{(a+b-i)!(a+c-i)!}
$$
### 洛谷 8114. 「Cnoi2021」六边形战士
如将匹配的一对三角形理解成一个菱形，那么问题就变成了菱形划分计数。
### 「ZJOI2022」计算几何
注意到题目中的点可以当成六边形网格的对偶图的边，这样问题就变成了上一题。
要特殊处理一下 $a+b\le c$。
## 「JOISC 2016 Day 1」棋盘游戏
难度：T3。
矩阵外视为空格。
那么首先，第一三行不能有连续的两个空格，否则无解。从而第一三行的空格随时可以填上。
这样，考虑将第二行划分为空格的极长连续段，不难发现连续段之间是独立的。
对每个连续段 DP，从左往右，记录 $f(i,j), g(i,j)$ 表示第二行第 $i$ 列的格子在前 $i$ 列中第 $j$ 个被通过上下/左右填上的方案数。
为了避免重复，钦定四个方向都有棋子的选择其中一种。
转移不太难编，但是需要比较细致。
## 「ABC253Ex」We Love Forest
难度：T3。
考虑计算每个点集的导出子图的生成树个数。
- 可以先假定连边具有顺序，然后枚举最后一条边连接的两个连通块。这是 $O(3^n)$。
- 可以直接使用矩阵树定理。则为 $O(n^3 2^n)$。
- 可以使用**集合幂级数**与**逐点牛顿迭代法**（这题就是 EI 论文的例题）。则为 $O(n^2 2^n)$。
考虑计算答案，不难转化为计算 $k=1,\dots,n-1$ 棵树的方案数。
- 可以暴力实现子集卷积。这是 $O(n 3^n)$。
- 可以正常实现子集卷积。则为 $O(n^3 2^n)$。
- 此问题也是 **EGF 复合集合幂级数**的**转置问题**。则为 $O(n^2 2^n)$。
综上，此题可以在 $O(n^2 2^n)$ 的复杂度内解决。
## 「CSP-S 2019」Emiya 家今天的饭
难度：T2。
正面不好直接计算，但是反面是容易做的，因为最多有一种主要食材违背条件。
枚举这种食材，那么状态只需要记录其出现次数与其余出现次数的差即可。
$O(n^2 m)$。
## 洛谷 1393. Mivik 的标题
难度：T3.5。
一道有趣的典题。
考虑容斥，钦定存在若干次匹配，每次匹配贡献 $-1$ 的系数，对此求和即得答案。
带着容斥系数 DP，设计算到前 $i$ 位的容斥系数和是 $f(i)$，且以一次匹配结尾，那么转移可能是：
- 紧接着一次。这样的转移会使得 $i$ 延伸所有周期长度（周期 $=$ $|S|$ $-$ border）。
- 新开一次。这样的转移会使得 $i$ 带着 $|\Sigma|$ 往后延伸若干位（非钦定的字符串）后延伸长度位。
我们知道周期是 $O(\log |S|)$ 个等差数列，从而只需要维护 $O(\log |S|)$ 个桶用来处理同余前缀和即可。
$O(n \log |S|)$。
## 「CF891E」Lust
难度：T2.5。
众所周知，这个贡献是 $\prod a_i$ 之差。因此我们只要算出最后 $\prod a_i$ 的期望。
采用 EGF，我们考虑一个 $i$ 的所有操作的贡献：
$$
F_i(x) = \sum_{j\ge 0} \frac{(a_i-j)(x/n)^j}{j!} = (a_i - x/n) \mathrm e^{x/n}
$$
则答案就是 $\prod_{i=1}^n a_i - [x^k/k!] \prod_{i=1}^n F_i(x) = \prod_{i=1}^n a_i - [x^k/k!] \mathrm e^x \prod_{i=1}^n (a_i - x/n)$。
容易做到时间复杂度 $O(n^2)$。如使用分治 MTT，可以做到 $O(n\log^2 n)$。
## 「CF1605F」PalindORme
难度：T4。
判定合法并不难：每次找到一对相同的数，从所有数中删掉这两个数和这两个数为 $1$ 的位，直到剩下 $0$ 或 $1$ 个数。
但是这个判定方法并不能为我们带来一个计数的方法，我们只能考虑从一般性的结构入手。
接下来有一句显然的话：如果一个序列不合法，那么其必然是在操作完一个合法序列后剩下两两不同的数。
但是，这就为我们指明了计数方法。
接下来就比较简单了，但是我懒得把转移抄过来了，建议自己看看别的题解（）
时间复杂度 $O(n^4)$。
## 「ZJOI2016」小星星
难度：T3。
对于排列问题，总有一个 $O(n^3 3^n)$ 的状压暴力。
如使用子集卷积，可以变成 $O(n^5 2^n)$，但还不够。
我们发现，排列的限制过于强了，但是若无须是排列则复杂度会下降许多。
那么，容斥即可。时间复杂度 $O(n^3 2^n)$。
## 「CF1326F2」Wise Men
难度：T3。
对答案容斥，也就是钦定一些 $1$，即钦定一些链。
先算出每个点集生成子图的生成链数。
枚举划分数，用子集卷积计算答案即可。注意到因为是划分，这里天然带了占位多项式，故只需要正常或卷积。
## 「CF53E」Dead Ends
难度：T3。
容斥，那么需要解决各点集生成子图的生成树个数。
前面已经提到过，采用**集合幂级数**与**逐点牛顿迭代法**。则为 $O(n^2 2^n)$。
## 「ZJOI2022」树
难度：T2.5。
进行一个子集容斥，钦定叶子集合，展开计算式：
$$
\sum_{S,T\subseteq U, S\cap T = \varnothing} f(S) g(T) (-2)^{|S\cap T|}
$$
转换计算顺序（按编号考虑各点属于 $S$ 还是 $T$ 还是两者皆否），使用 DP 计算和式即可。
## 「CF1060F」Shrinking Tree
难度：T4。
时间倒流。
初始时点权为 $1$，考虑随机边的排列，依次连边，并给两边的连通块各点的点权乘 $1/2$，答案就是每个点的期望点权。
枚举根结点，只计算根结点的贡献。那么，考虑一条边对根结点有贡献，当且仅当其到根路径上其他边都在其之前被加入。
考虑枚举哪些边有贡献，然后我们给每条边建一个点构成新图（不包括原图的点），若钦定某条边在另一条边之前被加入，则连有向边代表小于号。
为了确保仅由这些边贡献，我们还要连一些边使得其余的边没有贡献。
这样我们就得到了一张树形图，那么其方案数就是拓扑序计数，这是经典的，参见 CTS2019 氪金手游。
于是，我们采用 DP 优化此过程即可。
时间复杂度 $O(n^3)$。但是精度不太行。
## 「AGC041F」Histogram Rooks
难度：T4。
先容斥，**钦定** $k$ 个位置不被覆盖，容斥系数为 $(-1)^k$。那么就相当于 ban 了若干列和若干行连续段。
注意到，列总是连续的，因此我们先**枚举**这个**钦定**的过程中 ban 了哪些列。记为集合 $S$。
也就是说，$S$ 的列中必然各至少有一个位置被**钦定**为不被覆盖。
但是，这个**枚举**的过程依然比较难做。我们不妨再次**钦定**有若干列被**枚举**了但实际上其中没有格子被**钦定**不被覆盖。记为集合 $T \subseteq S$，则容斥系数为 $(-1)^{|T|}$。
那么，能**钦定**不被覆盖的格子就仅有 $S\setminus T$ 中的列中的格子了。
考虑贡献，若某个行连续段共有 $m$ 列，其中 $S$ 有 $p$ 列，$T$ 有 $q$ 列，则贡献为：
- 不**钦定**格子不被覆盖，并放置棋子：$2^{m-p}$。
- **钦定**某些格子不被覆盖，则该连续段被 ban：$\sum_{i\ge 1} \binom{p-q}i (-1)^i = -[p\ne q]$。
从而考虑在笛卡尔树上 DP，我们就有了树形结构来合并答案，设 $f(u, p, [p\ne q])$，则容易转移。
时间复杂度 $O(n^2)$。
## 「JOISC 2018 Day3」安全门
难度：T4。
左括号转为 $1$，右括号转为 $-1$。
令 $S_i$ 为前缀和。
假设翻转了 $[l,r]$，则 $S_n - 2S_r + 2S_{l-1}=0$，即 $S_r = S_{l-1} + S_n/2$。
且前缀和变为
\begin{cases}
Si, & 0 \le i < l \
2S{l-1}-S_i, & l \le i \le r \
S_i - S_n, & r < i \le n
\end{cases}
我们定义从左往右或者从右往左（注意从右往左的时候括号也要翻转）的前缀和合法，当且仅当全部 $\ge 0$。
那么，一个括号序列合法当且仅当两侧前缀和都合法。
分类讨论。
若两侧前缀和都合法，则可以直接 $O(n^2)$ 或 $O(n^3)$ DP 算出。
若恰有一侧前缀和不合法，不妨设是从左往右。
考虑取前缀和第一次变为 $-1$ 之前的最大前缀和（显然，至少会有一个 $-1$），设为 $A$。再令 $B=S_n$。
由于后一侧前缀和合法，因此 $S_n - S_i = B - S_i \le 0 \iff S_i \ge B$。因而 $B < 0$，否则该侧前缀和已经合法。
从而直接覆盖了限制三。
于是我们自然是取 $A$ 作为 $S_{l-1}$ 最优，并取其后的**第一个** $A+B/2$ 作为 $S_r$，且要求此部分均 $\le 2A$。
考虑枚举第一个 $-1$ 的位置，则若 $A+B/2 \ge 0$，$l,r$ 都在其左侧，显然区间内也一定 $\le 2A$，右侧只需 $\ge B$。否则，需要其右侧存在一个合法的 $r$。
左侧的方案数是好计算的。考虑将右侧全体前缀和减去 $B$，则要求：
- $S_i = -B-1$，$S_n=0$。
- $S_i, S_{i+1}, \dots, S_n \ge 0$。
- $S_i$ 到其后第一个 $S_r = A-B/2$ 中所有数 $\le 2A-B = 2(A-B/2)$。
枚举 $A-B/2$ DP 即可。
若两侧均不合法，取 $C=S_n$，$A$ 为第一次 $-1$ 前的最大值，$B$ 为最后一次 $C-1$ 后的最大值。
显然，$\ge 0$ 的前缀和 $\ge C$ 的后缀是不交的，否则必然有其中一侧前缀和合法。反之亦然，因此这样是充要的。
那么，不妨设 $A+C/2\le B$（否则可以倒过来求，但不要再次计算 $A+C/2=B$），则取 $A$ 与最后一次 $C-1$ 后的第一个 $A+C/2$ 即可。
枚举第一个 $-1$ 的位置为 $i$，记 $j$ 为最后一次 $C-1$ 的位置，左侧依然是好算的，右侧同样考虑减去 $C$，则要求：
- $j$ 变为最后一次 $-1$ 的位置。
- $S_i = -C-1$，$S_n = 0$。
- $S_i$ 到 $j$ 后第一个 $S_r = A-C/2$ 中所有数 $\le 2A-C = 2(A-C/2)$。
类似地，枚举 $A-C/2$ DP 即可。
时间复杂度 $O(n^3)$。
## XXII Open Cup, Grand Prix of Southeastern Europe. LIS Counting
> **简要题意.**
>
> 给定 $N,M$，对于 $1 \le pos,val \le NM$，计算最长上升子序列和最长下降子序列长度分别等于 $N$ 和 $M$ 的 $NM$ 阶排列 $p$ 中 $p_{pos}=val$ 的个数。
> 对大质数取模。
>
> $NM \le 100$。
难度：T4。
考虑一个不太一样的双射。
令 $inc_i,dec_i$ 分别为 $i$ 结尾的最长上升和下降子序列长度，那么我们维护两个 $N\times M$ 的矩阵 $A,B$，令 $A_{inc_i,dec_i}=i,B_{inc_i,dec_i}=p_i$。
可以发现 $A$ 是行列单调增，$B$ 是行单调减列单调增，并且一对 $(A,B)$ 和 $p$ 是双射。
因此我们 DP 刻画出 $A$ 的形态，设 $f_s$ 表示填至形状为 $s$ 的方案数，其中 $s$ 是 $N \ge a_1 \ge a_2 \ge \dots \ge a_M \ge 0$ 的 $(a_1,a_2,\dots,a_M)$，共有 $\binom{N+M}N$ 种。
则 $f(pos,val)$ 就是在 $A,B$ 的对应位置上分别是 $pos$ 和 $val$ 的 $(A,B)$ 对数。这可以用 $f$ 统计的结构拼出。
时间复杂度 $\Theta\left(\binom{N+M}N NM + (NM)^3\right)$。
## Petrozavodsk Summer 2020. Day2. SPb SU LOUD Enough Contest. Justice For Everyone
> **简要题意.**
>
> 给定长为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$ 和 $b_1, b_2, \dots, b_n$。
> 每个时刻你需要执行操作：选定下标 $i, j$ $(i < j)$，将 $a_i \gets a_i+1$，$a_j \gets a_j+1$，但需要保证任意时刻 $a$ 中的数两两不同。
> 问得到 $b$ 的方案数。
>
> $n \le 30$，$a_i, b_i \le 200$。
难度：T4。
自然 $a$ 和 $b$ 的排列顺序要相同，且 $\sum a_i - \sum b_i$ 是偶数。
于是不妨设 $a_1 < a_2 < \dots < a_n$，$b_1 < b_2 < \dots < b_n$，令 $t = (\sum a_i - \sum b_i)/2$。
据 LGV 引理，考虑先算出忽略互不相同的方案数，然后通过带符号求和算出答案。
令 $d_i = b_i - a_i$，那么方案数只跟此序列相关。
考虑数出有 $2t$ 次操作的方案数，要求 $2k-1$ 次与 $2k$ 次不同，然后除以 $2^t$。
这自然考虑容斥，枚举 $c_i$ 表示有 $c_i$ 对 $(2k-1,2k)$ 同时操作了 $i$，就是
$$
\sum_{0 \le c_i \le d_i/2} (-1)^{\sum c_i} \binom{t}{c_1, c_2, \dots, c_n, t-\sum c_i} \binom{2\left(t-\sum c_i\right)}{d_1 - 2c_1, d_2 - 2c_2, \dots, d_n - 2c_n}
$$
套路地，枚举 $\sum c_i$ 统计答案，即可表为 $n$ 个仅与 $d_i$ 相关的多项式的卷积的系数的线性组合：
$$
2^{-t}t! \sum_{s\ge 0} \frac{[2(t-s)]!}{(t-s)!} [x^s] \prod_{i=1}^n \sum_{0\le j \le d_i/2} \frac{(-x)^j}{j!(d_i-2j)!}
$$
记为 $F_{d_i}(x)$。
考虑带上符号求和，显然只需要构造矩阵 $M_{i,j} = F_{b_j-a_i}(x)$，计算 $\det M$ 系数的线性组合即可。
由于卷积的代价比较高，所以考虑代入点值再插值得到多项式。
时间复杂度 $O(n^4 \max b_i + n^2 (\max b_i)^2)$。
## Petrozavodsk Summer 2021. Day 3. IQ test by kefaa2, antontrygubO_o, and gepardo. Joke
> **简要题意.**
>
> 对于 $n$ 阶排列 $p,q$，称一个 $2n$ 阶排列 $r$ 合法当且仅当：
>
> - $r_1,r_2,\dots,r_n$ 离散化后等于 $p$。
> - $r_{n+1},r_{n+2},\dots,r_{2n}$ 离散化后等于 $q$。
>
> 记 01 串 $s$，其中 $s_i = [r_i < r_{n+i}]$，令 $f(p,q)$ 为所有合法的 $r$ 生成的本质不同的 $s$ 的个数。
> 给定 $p$ 和含空位的 $q$，求所有 $q$ 的 $f(p,q)$ 之和，对 $998244353$ 取模。
>
> $n \le 100$，也可以出到 $n \le 500$。
难度：T3.5。
注意到我们可以把问题变成 $p=[1,2,\dots,n]$ 的情况，问题得以简化。
接下来证明 $f([1,2,\dots,n],q)$ 就是 $q$ 的上升子序列个数。
考虑对于 $s$ 判断是否有方案。将所有小于关系连边，判断是否有环即可。同时可以发现如果有环，一定有长为 $4$ 的环。
考虑通过 $q$ 构造合法的 $s$：按照元素从大到小考虑对应位置是 $\texttt 0$ 还是 $\texttt 1$，如果是 $\texttt 0$ 则可以直接删除该位置而无影响；否则要删去一整个后缀。
将第二类操作对应上升子序列的元素，从而将 $q$ 删空的方案数就是 $q$ 的上升子序列个数。
不过据说这是偏序集的序理想，与反链构成双射。但是我还不太懂。
接下来可以做到 $O(n^3)$，设 $f(i,j,k)$ 表示考虑了前 $i$ 个数，目前的上升子序列以 $j$ 结尾，填了 $k$ 个问号的方案数即可。
## 「2020-2021 集训队作业」Game on Tree
难度：T4。
设 $F_u(i,j)$ 表示 $u$ 子树内 $A,B$ 的最优收益达到了 $i,j$ 的方案数，$X_u(i),Y_u(i)$ 表示 $A,B$ 收益不超过 $i$ 的方案数。
讨论 $u\in A$ 的转移，$B$ 中对称。
我们有
$$
F_u(i,j) = F_l(i,j) X_r(i) + F_r(i,j) X_l(i)
$$
和
$$
\begin{aligned}
X_u(i) &= 2 X_l(i) X_r(i) \\
Y_u(i) &= Y_l(i) 2^{|A_r|+|B_r|} k^{2|L_r|} + Y_r(i) 2^{|A_l|+|B_l|} k^{2|L_l|}
\end{aligned}
$$
如此即可 $\Theta(n^3)$ 解决问题。
首先注意到 $X_u,Y_u$ 分别是多项式。但是 $F_u$ 是二元多项式，这不好。
然而，或许与其纳什均衡的背景相关，$F_u(i,j)$ 的两元其实是独立的。有
$$
F_u(i,j) = U_u(i) V_u(j)
$$
且可以归纳证明
$$
\begin{aligned}
X_u(i) &= 2^{|A_u|} k^{|L_u|} U_u(i) i \\
Y_u(i) &= 2^{|B_u|} k^{|L_u|} V_u(i) i
\end{aligned}
$$
且可以验证 $u\in A$ 时 $U_u,V_u$ 有递推式
$$
\begin{aligned}
U_u(i) &= U_l(i) U_r(i) i \\
V_u(i) &= V_l(i) 2^{|A_r|} k^{|L_r|} + V_r(i) 2^{|A_l|} k^{|L_l|}
\end{aligned}
$$
从而这样计算点值，最后插出一项点值即可。
这样即可 $\Theta(n^2)$。
如果使用 NTT，结合转置原理和链分治也可以做到 $O(n \log^2 n)$。
## Petrozavodsk Winter 2017. Day2. Xiaoxu Guo Contest 5. City United
> **简要题意.**
>
> 给定 $n$ 个点的无向图，求有多少个点集的导出子图是连通的，但 $\bmod 2$。
>
> $n \le 50$，$(u, v) \in E \implies |u-v| \le 13$。
难度：T3。
考虑一个点集，若其包含 $k$ 个连通块，那么给其染黑白色使得黑色点与白色点之间没有连边的方案数为 $2^k$。
于是不妨考虑计算 $\bmod 4$ 的结果，这样 $k > 1$ 的都会变成 $0$。
大力状压 DP，最后除以 $2$ 即可。
## Petrozavodsk Winter 2017. Day2. Xiaoxu Guo Contest 5. Permutation and noitatumreP
> **简要题意.**
>
> 对排列 $p$，令 $q = (p_1, \dots, p_n, p_n, \dots, p_1)$，称 $p$ 合法当且仅当 $q$ 不存在子结构 $(1,4,2,3)$（即不存在子序列离散化后等于 $(1,4,2,3)$）。
> 问有多少 $n$ 阶排列是好的。
>
> $n \le 10^9$。
难度：T3。
~~2017 年整式递推远处求值还不普及，所以这应该最多是个线性递推！然后扔进 BM 或者 OEIS，做完了（雾）~~
设 $f_n$ 为答案，分类讨论转移。
若 $p_1 = n$，则这个位置没用。贡献为 $f_{n-1}$。
若 $p_1 = n-1$，那 $n$ 必须在 $p_2$。贡献为 $f_{n-2}$。
若 $p_1 = 1$，那可以发现必然是 $(1, 2, \dots, n-2, n-1, n)$ 或 $(1, 2, \dots, n-2, n, n-1)$。贡献为 $2$。
若 $p_1 = i \in [3, n-2]$，再讨论 $p_2$：
- 若 $p_2 = 1$，则会有 $(p_2,n,2,p_1)$。
- 若 $p_2 \in [2, i-1]$，则会有 $(1,n,p_2,p_1)$。
- 若 $p_2 \in [i+2, n-1]$，则会有 $(p_1,n,i+1,p_2)$。
- 若 $p_2 = n$，则会有 $(p_1,p_2,i+1,i+2)$。
于是 $p_2=i+1$。同理，会有一段连续上升的前缀被固定。
贡献为 $\sum_{i=2}^{n-3} 2f_i$。
若 $p_1 = 2$，同理，$p_2 \in \{1, 3\}$。
手玩一下，必形如 $(2,3,\dots,k-1,k,1,k+1,\dots,n-2,n-1,n)$ 或 $(2,3,\dots,k-1,k,1,k+1,\dots,n-2,n,n-1)$。
贡献为 $2(n-1)$。
综上，将递推式化简后可得
$$
f_n = 2f_{n-1} + f_{n-3} + 2 \quad (n \ge 4)
$$
执行线性递推远处求值即可。当然也可以矩阵快速幂。
## XXI Open Cup, Grand Prix of Tokyo. Ascending Matrix
> **简要题意.**
>
> 给定 $N,M,K,R,C,V$，计数 $N\times M$ 的矩阵 $a$，满足：
>
> - $1 \le a_{i,j} \le K$ $(1 \le i \le N, 1 \le j \le M)$。
> - $a_{i,j} \le a_{i,j+1}$ $(1 \le i \le N, 1 \le j < M)$。
> - $a_{i,j} \le a_{i+1,j}$ $(1 \le i < N, 1 \le j \le M)$。
> - $a_{R,C}=V$。
>
> $N,M \le 200$，$K \le 100$。
难度：T3。
自然考虑每种值的下轮廓线，然后将第 $i$ 条路径向右向下平移 $i$ 格，使用 LGV 引理即可统计不考虑最后一个限制的方案数。
考虑最后一个限制，也就是经过其左上方的路径数恰有 $V-1$ 条。带个 $x$ 计算行列式即可。
如果插值，则为 $O(K^2(N+M)+K^4)$。
根据 EI 的方法，将 $|A+Bx|$ 归约为求解特征多项式，其实也是可以 $O(K^2(N+M+K))$ 的。
## XXI Open Cup, Grand Prix of Tokyo. Sum Modulo
> **简要题意.**
>
> 给定 $N,M,K$ 和序列 $A_1, A_2, \dots, A_N$，有一个变量 $X$ 初始为 $0$，接下来每一步将会以正比于 $A_v$ 的概率使 $X \gets (X+v) \bmod M$，问得到 $K$ 的期望步数。
>
> $N\le 500$，$M \le 10^{18}$，$A_i \le 100$。
难度：T3。
DP，设 $f_i$ 表示从 $0$ 到 $i$ 的期望步数，反过来变成从 $i$ 到 $0$ 的期望步数，有
$$
\left\{
\begin{aligned}
f_0 &= 0 \\
f_i &= 1+\sum_{j=1}^N p_j f_{(i-j)\bmod M} \quad (0 < x < M)
\end{aligned}
\right.
$$
一个关键的性质是，有
$$
f_i = 1+\sum_{j=1}^N p_j f_{i-j} \quad (i \ge N)
$$
这是一个常系数线性非齐次递推。容易化为齐次递推：
$$
f_i = f_{i-1} + \sum_{j=1}^{N+1} (p_j-p_{j-1}) f_{i-j} \quad (i > N)
$$
从而我们可以用 $f_0, f_1, \dots, f_N$ 表出任意 $f_i$；进一步，只需 $1, f_0, f_1, \dots, f_{N-1}$。
那么我们求出 $f_{M-N,\dots,M-1}$ 的表示（可以先用快速幂算出 $x^{N-M} \bmod P(x)$，然后每次乘 $x$ 后取模，其中 $P(x)$ 是特征多项式），即可解出 $f_0, f_1, \dots, f_{N-1}$。
然后执行线性递推远处求值即可得到 $f_K$。
时间复杂度 $O(N^3 + N^2 \log M)$。
## Petrozavodsk Winter 2009. Day 7: Ural SU Contest. Aztec Treasure
> **简要题意.**
>
> 给定 $n\times m$ 的网格图，求完美匹配个数模 $10^9+7$。
>
> $n,m\le 100$。
难度：T4。
假设 $n,m$ 同阶。
二分图完美匹配计数是计算积和式，考虑给竖边乘 $i$，就变成一个 $nm/2$ 的方阵的行列式求值。
接下来考虑优化消元，考虑让第 $(i,j)$ 行只剩 $(1,1),(1,2),\dots,(1,m)$ 和 $(i+1,j)$ 这些位置，容易做到 $O(n^3)$。
这个做法是比较 NOIP 的，但是我们可以做得更有趣一些。
以下参考自唐老师的[文章](https://blog.csdn.net/skywalkert/article/details/65546892)和[这里的 J](https://qoj.ac/download.php?type=attachments&id=818&r=1)。
考虑正常做 FKT，令竖向边全部向下，奇数行的横向边向右，偶数行向左，这样归约到求 Pfaffian。
$n=3,m=4$ 的一个例子如下：（将 $(i,j)$ 编号为 $i+(j-1)n$）
$$
\begin{bmatrix}
& 1 & & 1 \\
-1 & & 1 & & -1 \\
& -1 & & & & 1 \\
-1 & & & & 1 & & 1 \\
& 1 & & -1 & & 1 & & -1 \\
& & -1 & & -1 & & & & 1 \\
& & & −1 & & & & 1 & & 1 \\
& & & & 1 & & −1 & & 1 & & −1 \\
& & & & & −1 & & −1 & & & & 1 \\
& & & & & & −1 & & & & 1 \\
& & & & & & & 1 & & −1 & & 1 \\
& & & & & & & & −1 & & −1
\end{bmatrix}
$$
取 $U = \left\{[i+1=j]-[i=j+1]\right\}_{i,j=1}^n$，$V = \left\{[i=j](-1)^{i-1}\right\}_{i,j=1}^n$，可以发现该矩阵分块后可得
$$
\begin{bmatrix}
U & V \\
-V & U & V \\
& -V & U & V \\
& & -V & U
\end{bmatrix}
$$
可以归纳证明，该矩阵的行列式和 Pf 等于 $n$ 阶方阵 $(-1)^{nm/2} F_m$ 的对应值。其中
$$
F_0 = I, F_1 = U, F_m = U \cdot F_{m-1} - F_{m-2} \quad (k\ge 2)
$$
注意到 $U$ 是特殊的，所以这部分可以 $O(n^3)$ 解决。
事实上，该递推也可以描述为 $2n$ 阶矩阵的高次幂，且其特征多项式也可以递推得到，所以大概可以在 $n,m$ 不同阶的时候做到更好。
接下来有另外一个做法。
首先多米诺骨牌覆盖计数有一个著名公式
$$
\prod_{j=1}^m \prod_{k=1}^n \left(4\cos^2\frac{j\pi}{m+1} + 4\cos^2\frac{k\pi}{n+1}\right)^{1/4}
$$
设 $r_n(k) = 2\cos\left(\frac{k\pi}{n+1}\right)$，原式可以化为
$$
\begin{aligned}
&= \prod_{j=1}^m \prod_{k=1}^n \left(r_m^2(j)-i^2r_n(k)\right)^{1/4} \\
&= \prod_{j=1}^m \prod_{k=1}^n \left(r_m(j)-ir_n(k)\right)^{1/4}\left(r_m(j)+ir_n(k)\right)^{1/4}
\end{aligned}
$$
设 $F_m(x) = \prod_{k=1}^n (x-r_n(k))$，注意到 $r_m(j)+r_m(m-j+1)=0$，原式可以继续化为
$$
\begin{aligned}
&= \prod_{j=1}^m F^{1/4}(i r_m(j))^{1/4} F^{1/4}(-i r_m(j)) \\
&= \prod_{j=1}^m F^{1/4}(i r_m(j))^{1/4} F^{1/4}(i r_m(m-j+1)) \\
&= \prod_{j=1}^m F^{1/2}(i r_m(j)) \\
\end{aligned}
$$
事实上，这个 $F(x) = U_n(x/2)$，其中 $U_n(x)$ 是第二类切比雪夫多项式。
关于切比雪夫多项式，有一个结论
$$
U_n(x) = \det(2xI + A), A = \{[|i-j|=1]\}_{i,j=1}^n
$$
因此
$$
\prod_{j=1}^m F(i r_m(j)) = \prod_{j=1}^m \det(i r_m(j)I + A/2) = (-i)^{nm} \det\left(\prod_{j=1}^m(iA/2 - r_m(j)I)\right)
$$
这里又出现了一个 $U_m(iA/2)$，因此我们考虑如何求这个。我们有
$$
U_0(x)=1, U_1(x)=2x, U_m(x) = 2xU_{m-1}(x) - U_{m-2}(x) \quad (m\ge 2)
$$
从而我们就得到了和上一种做法十分相似的结论。
## 「雅礼集训 2017 Day11」PATH
难度：T3。
经典的（类）LGV 做法在前面的题里已经叙述过，但也有必要了解另外一个做法。
不妨将坐标看成二维矩阵上的一条轮廓线，则每次轮廓线恰会拓展一格。将每个格子标号为其被拓展的时间，这就是一个杨表。
套用钩子公式，卷积即可。
## 「CF1530F」Bingo
难度：T3。
直接容斥是 $\tilde O(2^{2n+2})$ 的，难以接受。
考虑容斥行和对角线，列直接计算。容易做到 $O(n2^{n+2})$。
## 「AGC060D」Same Descent Set
难度：T3.5.
考虑一对 $(P,Q)$ 的合法条件是
$$
\prod_{i=1}^{N-1} (1-[P_i<P_{i+1}]-[Q_i<Q_{i+1}]+2[P_i<P_{i+1}][Q_i<Q_{i+1}])
$$
也就是说，各在 $P,Q$ 中钦定 $S,T$ 内的下标是小于号，贡献是 $(-1)^{|S|+|T|} 2^{|S\cap T|}$。
考虑交不好算，拆成 $2^{|S|+|T|-|S\cup T|}$，即 $(-2)^{|S|+|T|} 2^{-|S\cup T|}$。
我们考虑先在 $P, Q$ 中各自钦定一些连续上升段（暂且不管 $2^{-|S\cup T|}$ 的贡献），然后点乘。设我们得到一个 OGF $G(x)$，那么各个极长的 $P,Q$ 上升段的并的 OGF $F(x)$ 就应该满足
$$
\frac F{1-F} = G \iff F = \frac G{1+G}
$$
这样我们就解决了并的问题：在得到的 $F$ 中点乘 $2^{-(k-1)}$ 即可。然后再进行一次求逆就能得到答案。
不过若我们考虑翻转 $Q$ 的大小关系，容斥信息变为 $\prod ([P_i<P_{i+1}]+[Q_i<Q_{i+1}]-2[P_i<P_{i+1}][Q_i<Q_{i+1}]$，就可以省去一次求逆。
## 「PA 2019 Final」Grafy
> **简要题意.**
>
> 计数 $N$ 个有标号点，每个点的出入度都是 2 的有向简单图。
>
> $N \le 500$。
难度：T3。
不妨看做计数 $\{0, 1, \dots, 2N-1\}$ 的排列 $p_0, p_1, \dots, p_{2N-1}$，那么容斥信息就是
$$
\prod_{i=0}^{N-1}(1-[\lfloor p_{2i}/2\rfloor=i]-[\lfloor p_{2i+1}/2\rfloor=i]-[\lfloor p_{2i}/2\rfloor=\lfloor p_{2i+1}/2\rfloor]+2[\lfloor p_{2i}/2\rfloor=\lfloor p_{2i+1}/2\rfloor=i])
$$
钦定这三种元素出现，可得容斥式
$$
2^{-2N} \sum_{i+j+k\le N} 2^i (-1)^j (-1)^k \binom N{i,j,k,N-i-j-k} 2^i 2^{2j} \binom{N-i-j}k k! 2^k (2N-2i-j-2k)!
$$
时间复杂度 $O(N^3)$。
也存在[整式递推](https://www.luogu.com.cn/blog/your-alpha1022/pa-2019-finalgrafy-zheng-shi-di-tui)。
## 「2020-2021 集训队作业」Permutation
难度：T3.5。
首先转化题意，先计算出错排，那么问题变为 $\forall i,(p_i\ne i)\land(p_i \ne n-i+1)$ 的方案数。
将每对 $(i,n-i+1)$ 放在一起考虑，那么容斥无非就是钦定若干个位置满足了某个条件。发现一对这样的位置，钦定一个有 $4$ 种方案，钦定两个有 $2$ 种方案。
那么
- 若 $n=2k$，则答案为 $\sum_{n\ge 0} n! [x^n] (x^2-4z+2)^k$。
- 若 $n=2k+1$，则答案为 $\sum_{n\ge 0} n! [x^n] (x^2-4z+2)^k(x-1)$。
根据欧拉积分
$$
\int_0^{\infty} x^n \mathrm e^{-x} \,\mathrm d x = n!
$$
考虑设出
$$
\begin{aligned}
I_n &= \int_0^{\infty} (x^2-4x+2)^n \mathrm e^{-x} \,\mathrm d x \\
J_n &= \int_0^{\infty} x(x^2-4x+2)^n \mathrm e^{-x} \,\mathrm d x
\end{aligned}
$$
考虑用分部积分转化出递推式
$$
\begin{aligned}
I_n
&= \int_0^{\infty} (x^2-4x+2)^n \mathrm e^{-x} \,\mathrm d x \\
&= -\int_0^{\infty} (x^2-4x+2)^n (-\mathrm e^{-x}\,\mathrm dx) \\
&= -\int_0^{\infty} (x^2-4x+2)^n \,\mathrm d(\mathrm e^{-x}) \\
&= -\left.(x^2-4x+2)^n\mathrm e^{-x}\right|_0^{\infty} + \int_0^{\infty} \mathrm e^{-x} \,\mathrm d\left[(x^2-4x+2)^n\right] \\
&= 2^n + \int_0^{\infty} \left[(x^2-4x+2)^n\right]'\mathrm e^{-x} \,\mathrm dx \\
&= 2^n + \int_0^{\infty} n(x^2-4x+2)^{n-1}(2x-4) \mathrm e^{-x} \,\mathrm dx \\
&= 2^n - 4n I_{n-1} + 2n J_{n-1} \\
J_n
&= \int_0^{\infty} x(x^2-4x+2)^n \mathrm e^{-x} \,\mathrm d x \\
&= -\int_0^{\infty} x(x^2-4x+2)^n (-\mathrm e^{-x}\,\mathrm dx) \\
&= -\int_0^{\infty} x(x^2-4x+2)^n \,\mathrm d(\mathrm e^{-x}) \\
&= -\left.x(x^2-4x+2)^n\mathrm e^{-x}\right|_0^{\infty} + \int_0^{\infty} \mathrm e^{-x} \,\mathrm d\left[x(x^2-4x+2)^n\right] \\
&= \int_0^{\infty} \left[x(x^2-4x+2)^n\right]' \mathrm e^{-x} \,\mathrm d x \\
&= \int_0^{\infty} \left[(x^2-4x+2)^n+nx(x^2-4x+2)^{n-1}(2x-4)\right] \mathrm e^{-x} \,\mathrm d x \\
&= \int_0^{\infty} \left[(x^2-4x+2)^n+2n(x^2-4x+2)^{n-1}(x^2-2x)\right] \mathrm e^{-x} \,\mathrm d x \\
&= \int_0^{\infty} \left[(x^2-4x+2)^n+2n(x^2-4x+2)^{n-1}[(x^2-4x+2)+2x-2]\right] \mathrm e^{-x} \,\mathrm d x \\
&= I_n + 2n I_n + 4n J_{n-1} - 4n I_{n-1} \\
&= (2n+1) I_n - 4n I_{n-1} + 4n J_{n-1}
\end{aligned}
$$
## 「EI 论文题」矩阵树
> **简要题意.**
>
> 有⼀张图，总共有 $n = n_1 + \dots + n_k$ 个节点，我们依次称其为第 $1, 2, \dots , k$ 部分。
> 对于全体 $i$ 部分到 $j$ 部分的点对，两两之间有 $a_{i,j}$ 条边。输出这张图的⽣成树数量同余 $998244353$。
>
> $1 \le n \le 10^8$，$1 \le k \le 300$，$a_{i,j} = a_{j,i}$。
难度：T3.5。
论文里有多元拉反的做法，在此不表。
介绍一种更为朴素的做法：考虑 Laplacian 矩阵 $|D - AB^{\mathsf T}|$，其中 $D$ 是 $n$ 阶对角阵，$A, B$ 是 $n \times k$ 矩阵。
设 $S_i$ 为 $i$ 所处的类，则令 $A_{i, j} = [S_i = j]$，$B_{i, j} = a_{j, S_i}$，则 $AB^{\mathsf T}$ 就是其邻接矩阵。
根据 Matrix Determinant Lemma，有 $|D-AB^{\mathsf T}| = |D||I_k - B^{\mathsf T} D^{-1} A|$。
从而可以 $O(k^3)$ 计算。
## Petrozavodsk Winter 2019. Day5. Gennady Korotkevich Contest 4. Four Elements
> **简要题意.**
>
> 给定集合 $A = [l_1, r_1] \cup [l_2, r_2] \cup \dots \cup [l_n, r_n]$，问有多少从 $A$ 中选出 $4$ 个不同的整数的方案数使得和为 $s$。
>
> $n \le 400$，$s \le 8 \times 10^8$。
难度：T3。
令 $A(x) = \sum_{i=1}^n \frac{x^{l_i}-x^{r_i+1}}{1-x}$，则答案就是
$$
[x^s t^4] \prod_{i\ge 1} (1+tx^i)^{[x^i] A(x)}
$$
经过简单的 ln-exp 推导，可以得到
$$
[x^s t^4] \exp\left(\sum_{k\ge 1} \frac{(-1)^{k-1} t^k A(x^k)}k\right)
$$
展开得
$$
[x^s] \frac1{24} \left(A^4-6A(x^2)A^2+3A^2(x^2)+8A(x^3)A-6A(x^4)\right)
$$
除了第一项以外，显然都可以 $O(n^3)$。第一项可以在折半后通过 Vandermonde 恒等式和双指针计算，时间复杂度 $O(n^2 \log n)$。
## The 2021 CCPC Weihai Onsite. Subset
> **简要题意.**
>
> 选出 $\{0, 1, \dots, N\}$ 的一个 $K$ 元子集，使得异或和在二进制下有 $B$ 个 $1$。
> 计数方案数，取模 $998244353$。
>
> $N \le 10^9$，$K \le 5000$。
难度：T3.5。
记 $L = \lfloor \log_2 N \rfloor+1$。
考虑做 $2^L$ 长度的异或卷积，即
$$
[t^K] \prod_{S=0}^N (1+tx^S)
$$
其中 $t$ 元上是正常卷积，$x$ 元上是异或卷积。
做 FWT，则 $[x^V]$ 就是
$$
[t^K] 2^{-L} \sum_{T=0}^{2^L-1} (-1)^{|V\cap T|} \prod_{S=0}^N (1+(-1)^{|S\cap T|}t)
$$
若要对所有 $K$ 元子集求和，我们再引入元 $q$：
$$
[t^K q^B] 2^{-L} \sum_{T=0}^{2^L-1} (1-q)^{|T|} (1+q)^{L-|T|} \prod_{S=0}^N (1+(-1)^{|S\cap T|}t)
$$
假设给定 $T$，考虑计算有多少个 $1+t$ 和 $1-t$。
若 $N = 2^L-1$，则经典的结论是 $\sum_{S=0}^{2^L-1} [2 \nmid |S\cap T|] = [T \ne \varnothing] 2^{k-1}$，即奇偶恰各有一半。
从而我们可以将 $[0, N]$ 分解成若干长为 $2^k$ 的区间分别计算。
继续观察，注意到这个结果仅跟 $T$ 的最低位相关，因此仅有 $O(L)$ 种不同的结果。
从而容易 $O(KL)$ 计算出每一项的系数。
接下来考虑计算
$$
[t^K q^B] \sum_{i, j} a_{i,j} (1+t)^{b_i} (1-t)^{N-b_i+1} (1+q)^j (1-q)^{L-j}
$$
暴力计算，就是 $O((K+L)L) = O(K \log N + \log^2 N)$。
## Xmas Contest 2021. Homework From Zhejiang
> **简要题意.**
>
> 给定两张大小为 $M,N$ 的有向图 $G_1, G_2$，计算 $G = G_1 \square G_2$ 以各个点为根的外向树个数。其中 $\square$ 为笛卡尔积。
>
> $M, N \le 500$。
难度：T4。
先来考虑对于给定的一个点数为 $N$ 的有向图 $G$ 如何计算其各个点为根的外向生成树权值和。
记熟知的 Laplacian 矩阵为 $L$。根据 Matrix-Tree 定理，以 $u$ 为根的外向生成树权值和即为 $L_{uu}$ 处的主余子式。 也就是说，我们需要计算 $L$ 的伴随矩阵 $L^*$ 的对角线。
注意到 Laplacian 矩阵并不满秩，因此其伴随矩阵的秩不超过 $1$。因此，存在列向量 $x,y$ 使得其伴随矩阵 $L^* = xy^{\mathsf T}$。
而注意到 $L$ 所有行向量之和为全 $0$ 向量，从而可以证明其同一列的所有代数余子式相等，因此 $L^*$ 的各列向量相等，$y$ 可以取全 $1$ 向量。
那么，我们只需要算出 $x$ 即可获得对角线上的值。
而根据 $AA^* = |A| I$，可知 $L x y^{\mathsf T} = 0$，也就是 $L x=0$。据此，我们可以解出一个非平凡的 $x$，但其与真正的 $x$ 相差常数倍。
幸运的是，这是容易处理的。我们只需要取一个非 $0$ 的位置计算出对应的余子式即可。
接下来考虑一般情况。令 $L^{(1)},L^{(2)}$ 分别为 $G_1, G_2$ 的 Laplacian 矩阵，易得 $G_1 \square G_2$ 的 Laplacian 矩阵为 $L = L^{(1)} \otimes I_N + I_M \otimes L^{(2)}$。其中 $\otimes$ 为 Kronecker 积。
接下来，我们注意到，若我们对 $L^{(1)}, L^{(2)}$ 求出了各自的 $x^{(1)}, x^{(2)}$，则有 $L (x^{(1)} \otimes x^{(2)})=0$。因此我们也只需要定出相差的系数即可。
我们考虑通过其和，也就是伴随矩阵的迹来定出这个系数。
设 $L^{(1)}, L^{(2)}$ 有特征值 $\lambda_1, \lambda_2, \dots, \lambda_M$ 和 $\mu_1, \mu_2, \dots, \mu_N$，则 $x^{(1)}, x^{(2)}$ 的和即为 $L^{(1)}, L^{(2)}$ 的特征多项式的 $1$ 次项系数乘 $(-1)^{M-1}$ 和 $(-1)^{N-1}$。
注意到 $L^{(1)}, L^{(2)}$ 必有 $0$ 这个特征值，不妨设 $\lambda_1 = \mu_1 = 0$，则这个值就是 $\lambda_2 \lambda_3 \cdots \lambda_M$ 和 $\mu_2 \mu_3 \cdots \mu_N$。
因此 $x^{(1)} \otimes x^{(2)}$ 的和即为 $\lambda_2 \lambda_3 \cdots \lambda_M \mu_2 \mu_3 \cdots \mu_N$。
而可以证明，$L$ 的特征值为 $\lambda_i + \mu_j$ $(i=1,2,\dots,M, j=1,2,\dots,N)$（证明见 [1]）。因此，相差的系数即为
$$
\prod_{i=2}^M \prod_{j=2}^N (\lambda_i + \mu_j)
$$
而我们知道特征值是特征多项式的根，因此我们借助 Resultant，可以得到这个乘积的值为 $\operatorname{res}\left(\frac{|tI-L^{(1)}|}t, \frac{|tI+L^{(2)}|}t\right)$。
而对于 Resultant 的计算，由于这部分并非瓶颈，可以直接 $O((N+M)^3)$ 计算行列式。
也可以用多项式 Euclid 实现其求算。暴力实现就是 $O(NM)$ 的。
[1] 潘佳奇，浅谈线性代数与图论的关系，IOI 2021 中国国家集训队论文
## 「CF1792F」Graph Coloring
难度：T3.5。
先忽略不能全红或全蓝的条件，然后我们摘出红边所构成的子图。
接下来，我们注意到，当 $n\ge 2$，该图或补图必定恰有一者连通。
同时，若该图不连通，则其符合条件当且仅当各连通块都是符合条件的图。
因此，设连通的符合条件的图的 EGF 为 $F$，立刻写出
$$
2F - x = \mathrm e^F - 1
$$
牛顿迭代或在线卷积均可。当然如果你想直接套板子，也可以进行一步拉反。
事实上，EI 指出这样的图就是 $P_4$-free 图，即不存在四个点的路径的图。证明留作读者练习。
## 「THUPC2018」好图计数
难度：T3.5。
上一题的无标号版本。将 $\exp$ 改为 Polya Exp（即 Euler 变换）即可。
## Potyczki Algorytmiczne 2021, Runda 5. Zbiory niezależne [A]
> **简要题意.**
>
> 给定 $l, r, c$，计数最大独立集大小在 $[l, r]$ 内，各个点具有 $c$ 种可能的颜色的无标号无根树个数。
>
> $r \le 5 \times 10^5$，时限巨大。
难度：T3.5。
注意这个最大独立集不带权，因此我们可以贪心：如果儿子都不在最大独立集中就将父亲选入最大独立集中。
这样我们先记 $G, H$ 分别是根是否被选中的树的 OGF，借助 Polya Exp 可以写出方程
$$
\begin{cases}
H = cx \operatorname{Exp}(G) \\
G = c \operatorname{Exp}(G+H) - c \operatorname{Exp}(G) \\
\end{cases}
$$
考虑在线卷积维护 $\operatorname{Exp}(G)$ 和 $\operatorname{Exp}(G+H)$，借助洛谷 5900 的手法即可解决。
接下来我们依然考虑重心为根即可，不过题解使用的是本质相同的 Otter's Formula，或许更为方便。以下直接给出结论，设答案为 $F$，有
$$
F(x) = G(x) + H(x) - \frac12 G^2(x) + \frac12 G(x^2) - G(x) H(x) - \frac1{2x} H^2(x) + \frac1{2x} H(x^2)
$$
QOJ 上时限是 45s，我写了个 $O(r\log^2 r/\log\log r)$ 获得了 899ms 的好成绩。
## 「ARC155F」Directable as Desired
难度：T3.5。
给出一个代数解法。借鉴了 [Elegia 的思路](https://codeforces.com/blog/entry/111944?#comment-997984)。
建完全图，令 $(i, j)$ 带有边权 $x_i + x_j$，那么我们无非就是要算其 Laplacian 矩阵的任一主子式的 $[x^{d_1} x^{d_2} \dots x^{d_n}]$。
记 $s = \sum_i x_i$，$D = \operatorname{diag}(n x_i + s)$，$A_{i, 1} = B_{i, 2} = x_i$，$A_{i, 2} = B_{i, 1} = 1$。
则该图的 Laplacian 矩阵为 $L = D - AB^{\mathsf T}$。
不妨设 $d_n=0$，则考虑删去第 $n$ 行 $n$ 列，易知其仍然满足此形式。则根据 Matrix Determinant Lemma，有
$$
|D - AB^{\mathsf T}| = |D| |I_2 - B^{\mathsf T} D^{-1} A|
$$
展开整理可得
$$
\prod_i (nx_i + s) - 2 \sum_i x_i \prod_{j\ne i} (n x_j + s) + \sum_{i<j} (2x_ix_j - x_i^2 - x_j^2) \prod_{k\ne i, j} (n x_k + s)
$$
接下来的计算是容易的。
## 洛谷 9005. 「RC-07」超超立方体
难度：T3。
题目无非是给出 $G = K_{a_1} \mathop\square K_{a_2} \mathop\square \cdots \mathop\square K_{a_n}$，求其生成树个数。其中 $\square$ 为图的 [Cartesian 积](https://en.wikipedia.org/wiki/Cartesian_product_of_graphs)。
根据 Matrix-Tree 定理，我们知道答案即为其 Laplacian 矩阵的去掉一个零特征值后的特征值之积的 $(\prod a_i)^{-1}$ 倍。
而 $K_m$ 的 Laplacian 矩阵的特征多项式即 $\lambda(\lambda-m)^{m-1}$。
而根据 [1]，两张图的 Cartesian 积的 Laplacian 矩阵的特征值为 $\lambda_i + \mu_j$，其中 $\lambda_i, \mu_j$ 分别为各自的 Laplacian 矩阵的特征值。且容易推广多张图。
因此，考虑用生成函数计量最终的乘积式中各种特征值的贡献，也即计算多项式
$$
\prod_{i=1}^n (1 + (a_i-1)x^{a_i})
$$
的系数取模 $99824435\mathbf 2$ 的结果。本题中仅需 $O(n \sum a_i)$ 即可。
[1] 潘佳奇，浅谈线性代数与图论的关系，IOI 2021 中国国家集训队论文
## 「CSAcademy Round #35」Counting Quests
> **简要题意.**
>
> 从 $[1, N]$ 的所有子区间中选取若干个，问有多少种方案使得，对于任意 $x$ 都能通过得知各区间是否包含其这一信息确定。
>
> $N \le 300$，取模大质数。
难度：T4。
记 $S_i$ 表示覆盖了 $i$ 的区间集合。显然，我们只需 $S_i$ 互不相同。
然而，我们注意到，对于任意方案，相同的 $S_i$ 都是不会相交的，这是一个类似括号序的结构。
从而，我们能为任意的区间覆盖方案表达出一个树形结构。具体地，对于每个 $S_i$，我们取最后一个与其相同的 $S_j$，划分为一段 $[i, j]$。显然，我们可以通过这一方案恰好区分出每个数在哪一区间里。
我们考虑计数这一过程。记 $F(x)$ 为答案，$G(x) = \sum_{k\ge 0} 2^{\binom{k+1}2} x^k$ 为所有方案，则 $H(x) = \sum_{k\ge 1} 2^{\binom{k-1}2} x^k$ 为各区间内部的方案数（不可再选择触碰端点的区间），则我们有方程
$$
G(x) = F(H(x))
$$
暴力 DP 就有 $O(N^3)$。
也可以两边复合 $H^{\langle -1\rangle}(x)$，得到
$$
F(x) = G(H^{\langle -1\rangle}(x))
$$
求算 $[x^n]F(x)=[x^n]G(H^{\langle -1\rangle}(x))$ 可以直接使用扩展拉格朗日反演。就有 $O(N^2)$ 或 $O(N\log N)$。
## 「CTT 2018 Day1 T3」芒果冰加了空气
> **简要题意.**
>
> 给定一棵 $n$ 个点的树，求点分树方案数。
>
> $n \le 5000$。
难度：T3。
考虑连一条边 $(u, v)$ 导致**点分树合并**的过程，事实上与一般的数据结构合并是一致的：传入两个根结点，并考虑选择一个成为最后的根结点，将剩下的部分沿着 $u, v$ 所在的链递归。
因此，我们只需要记状态 $f_{u, i}$ 表示 $u$ 子树内的点分树，$u$ 的深度为 $i$ 的方案数。
转移时先对儿子的 DP 数组做后缀和，再合并。时间复杂度 $O(n^2)$。
## 「CTT 2019 Day1 T1」递增树列
> **简要题意.**
>
> 给定一棵 $n$ 个点的树，问有多少排列 $p$ 满足所有 $p_i, p_{i+1}$ 的 LCA 的深度不降。
>
> $n \le 80$。
难度：T3。
首先，可以证明，所有 $\operatorname{lca}(p_i, p_{i+1})$ 都具有祖先后代关系。否则，显然可以找到一个分界点不满足条件。
那么直接设 $f_{u, i}$ 表示 $u$ 子树内选择 $i$ 个点的方案数。转移的时候需要将其他子树的点与之合并，需要算一个限制某些点不能相邻的排列数。可以容斥。
时间复杂度 $O(n^4)$。
## 「雅礼集训 2017 Day8」共
难度：T3。
可以转化为完全二分图生成树计数，此处不表。
考虑直接上 EGF，用 $x, y$ 计量深度为奇数和偶数的点数。于是方程很简单，
$$
F = x \exp (y \exp F)
$$
我们只需要 $(N-1)! [x^K y^{N-K}] F$，考虑先对 $x$ 拉反，
$$
\begin{aligned}
(N-1)! [x^K y^{N-K}] F &= \frac{(N-1)!}K [x^{K-1} y^{N-K}] \exp(K y \mathrm e^x) \\
&= \frac{(N-1)!}{K(N-K)!} [x^{K-1}] K^{N-K} \mathrm e^{(N-K)x} \\
&= \frac{(N-1)!}{K(K-1)!(N-K)!} K^{N-K} (N-K)^{K-1} \\
&= \binom{N-1}{K-1} K^{N-K-1} (N-K)^{K-1}
\end{aligned}
$$
~~真丑，感觉不如二元拉反。~~
## Petrozavodsk Winter 2021. Day 7. North American Contest 1. Colorful Components
> **简要题意.**
>
> 给定 $n$ 个点，每个点具有颜色。你要将它们连接成树，使得任意同色极大连通块大小不超过 $k$。
>
> $n \le 300$。
难度：T3.5。
[懒得搬运了](https://www.luogu.com.cn/blog/your-alpha1022/ji-yi-ge-xiao-qiao-di-rong-chi-wen-ti)。