【题解】2025 四川省赛
挺匆忙的，到乐山就吃了一顿跷脚牛肉。
参赛体验的话，场地太热容易红温，蚊虫也多，除此之外都还好。
Mid 都不怎么开得出来啊，要努力加训了。
以下题解按个人主观难度排序。
I. 本质不同的后缀
逆序将每个字符串插进 Trie，最后 Trie 的结点数就是答案。
时间复杂度 \(O(\sum |S_i|\cdot 26)\)。
F. 逆序对
填 ? 的策略肯定是：存在一个分界点，分界点前的 ? 填 \(1\)，分界点后的 ? 填 \(0\)。
考虑先让所有 ? 都是 \(0\)，然后从左到右逐个变成 \(1\)，维护逆序对数。
只需要动态记录前缀 \(1\) 和后缀 \(0\) 的个数。
时间复杂度 \(O(n)\)。
H. 胡图图
\(X\) 轴和 \(Y\) 轴可以分开考虑。
令 \(f[i][0/1]\) 表示从 \(0\to i\) 走偶数/奇数步最少需要走几步，\(dx=|x-X|\)，\(dy=|y-Y|\)，则 \[ ans = \min\begin{cases}\max(f[dx][0],f[dy][0])\\ \max(f[dx][1], f[dy][1])\end{cases} \] 纸上列个表易得： \[ f[i][0]=\begin{cases} 0 &,i=0\\ 2\cdot \left\lfloor\dfrac{x-1}{4}\right\rfloor + 2 &,\text{otherwise} \end{cases} \] \[ f[i][1]=\begin{cases} 3 &,i=0\\ 2\cdot \left\lfloor\dfrac{x+1}{4}\right\rfloor + 1 &,\text{otherwise} \end{cases} \]
时间复杂度 \(O(1)\)。
J. 四川省赛
经典的树形 dp。
令 \(f[x][i=0\sim 4]/g[x][i=0\sim 4]\) 分别表示从 \(x\) 子树中的某处开始，直到 \(x\) 为止匹配了 SCCPC 中的前缀 \([0,i]\ /\) 后缀 \([i,4]\) 的方案数。
对于一个 \(x\)，答案有两类：
直接以 \(x\) 结尾，即 \(f[x][4]+g[x][0]\)。
以 \(x\) 为中转两个子树拼起来，枚举中转点 \(i\)，即
\[ \sum_{y\in son[x]}\sum_{i=1}^{3}f[y][i-1]\cdot (sg[i+1]-g[y][i+1]) \]
其中 \(sg[i]=\sum\limits_{y\in son[x]}g[y][i]\)。
时间复杂度 \(O(n)\)。
K. 点分治
正难则反，倒着扫描序列。
对于一个 \(x=p[i]\)，遍历 \(x\) 的邻居 \(y\)，如果 \(y\) 被访问过，设 \(y\) 所在连通块中 "在 \(p[i\sim n]\) 中最靠前的点" 为 \(z\)，则可以确定 \(x\) 是 \(z\) 的父亲，接着将 \(x\) 和 \(y\) 用并查集并起来。
不难发现，此时 \(y\) 所在连通块中 "在 \(\{p\}\) 中最靠前的点" 变成了 \(x\)。编写代码时，可以直接将当前扫描到的点作为新连通块的根，这样 \(z\) 就能直接 find 得到了。
时间复杂度 \(O(n\log n)\)。
A. 最小乘积
这道题的关键是想到：
- 状态设计：\(dp[x][i]\) 表示所有从 \(1\to x\) 的路径，路径上 \(\sum a\) 为 \(i\) 时，\(\sum b\) 的最小值。
- 转移顺序：外层枚举第二维，让 \(\sum a\) 小的状态先转移，不会出现环。
转移方程是朴素的： \[ dp[y][i + a] = \min_{x\to y}(dp[x][i] + b) \] 答案即 \(\min\limits_{i=1}^{n}(i\cdot dp[n][i])\)。
时间复杂度 \(O(nm\max\{a_i\})\)。
C. 最优时间
先把所有 \(i\in [1,n]\) 的 \(S(i)\) 处理出来。
暴力迭代，令 \(f[x]\) 表示 \(x\) 的答案，则 dp 转移如下： \[ f[i]=\min(f[i-1],\frac{\sum_{j\in S(i)}f[j-1]}{|S(i)|}) \] 迭代 \(100\) 次即可 AC。
官方题解证明了这个式子是收敛的，但并没有证明为什么是 \(100\) 次，问就是你说过没过吧。
时间复杂度 \(O(100\cdot n\log n+q)\)。
L. abc
我们用 \(c_{a/b/c}\) 表示 \(a/b/c\) 的出现次数。
最为关键的观察是： \[ \max(|c_a-c_b|,|c_a-c_c|,|c_b-c_c|)=\frac{|c_a-c_b| + |c_a-c_c| + |c_b-c_c|}{2} \] 于是，我们要求的变成了： \[ \frac{1}{2}(\sum_{T\in S}|c_a-c_b|+\sum_{T\in S}|c_a-c_c|+\sum_{T\in S}|c_b-c_c|) \] 这对吗？这不对。只有对满足 "\(a,b,c\) 均出现了" 的子串 \(T\) 来说，贡献才是正确的。
否则我们考虑我们把贡献算错了多少。
当 \(S\) 的某个子串 \(T\) 恰有 \(a,b,c\) 中的一种字符时，我们期望得到 \(0\)，但我们算成了 \(\dfrac{|c_a-0|+|c_a-0|+|0-0|}{2}=c_a\)（这里假设 \(T\) 只含 \(a\)），即多算了 \(c_a=|T|\)。
故我们要减去 \[ \sum_{T\in S,\ T \text{ 只含 } a,b,c \text{ 中的一种字符}} |T| \] 怎么算这个式子？
- 对于一个长为 \(n\) 的字符串，它的所有子串的长度之和为 \(\dfrac{n(n+1)(n+2)}{6}\)。
所以我们只用 \(O(n)\) 扫一遍，对每个极长单色段计算贡献。
当 \(S\) 的某个子串 \(T\) 恰有 \(a,b,c\) 中的两种字符时，我们期望得到 \(|c_a-c_b|\)（这里假设 \(T\) 只含 \(a,b\)），但我们算成了 \(\dfrac{|c_a-c_b|+|c_a-0|+|c_b-0|}{2}\)，多算了 \[ \frac{|c_a-c_b|+c_a+c_b}{2}-|c_a-c_b|=\frac{c_a+c_b-|c_a-c_b|}{2}=\min(c_a,c_b) \] 故我们要减去： \[ \sum_{T\in S,\ T \text{ 只含 }a,b}\min(c_a,c_b) +\sum_{T\in S,\ T \text{ 只含 }a,c}\min(c_a,c_c) +\sum_{T\in S,\ T \text{ 只含 }b,c}\min(c_b,c_c) \] 怎么算这个式子？
以第一项为例，它其实等于 \[ \frac{1}{2}\sum_{T\in S, T \text{ 只含 } a,b}|T|-|c_a-c_b| \] 搞不懂的话在纸上画两条线就搞懂了。
但这样还是很麻烦。实际上，我们还可以改写成 \[ \frac{1}{2}\sum_{T\in S, T \text{ 不含 } c}|T|-|c_a-c_b| \] 这是因为如果 \(T\) 只含一种字符的话，另一种字符的出现次数看作 \(0\)，即 \(\min(c_a,c_b)=0\)，完全不影响我们计数。
于是，枚举不含某个字符，找到极长连续段，计算贡献。
那现在最后的问题是，形如 \(\sum\limits_{T\in S}|c_a-c_b|\) 要怎么算。
将 \(a\) 看作 \(1\)，\(b\) 看作 \(-1\)，求前缀和，记作 \(\{pre\}\)，那么转化为了
\[ \sum\limits_{0\le i < j\le |S|}|pre[i]-pre[j]| \] 将 \(\{pre\}\) 排序，答案就是 \[ \sum_{i=1}^{n}(i\cdot pre[i]-\sum_{j=1}^{i-1}pre[j]) \] 扫一遍即可。
时间复杂度 \(O(n\log n)\)。
G. 丢番图
将方程写成矩阵的形式： \[ \begin{pmatrix} a_1^0 & a_2^0 & \cdots & a_n^0 \\ a_1^1 & a_2^1 & \cdots & a_n^1 \\ \vdots & \vdots & \ddots & \vdots \\ a_1^{n-1} & a_2^{n-1} & \cdots & a_n^{n-1} \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix} = \begin{pmatrix} t^0 \\ t^1 \\ \vdots \\ t^{n-1} \end{pmatrix} \] 可见系数矩阵 \(A\) 是范德蒙德矩阵的转置。
依据克莱姆法则，这个线性方程组的解为 \[ x_k=\frac{\det(A_k)}{\det (A)}\tag{1} \] 其中 \(A_k\) 是将矩阵 \(A\) 的第 \(k\) 列替换为列向量 \((t^0\ \ t^1\ \ \cdots \ \ t^{n-1})^{T}\) 后的新矩阵。
先看分母 \(\det(A)\)，依据行列式的性质有 \(\det(A)=\det(A^T)\)，而 \(A^{T}\) 是范德蒙德矩阵。于是
\[ \det(A) = \prod_{1 \le i < j \le n} (a_j - a_i) \] 再看分子 \(\det(A^k)\)，眼尖的你会发现这仍然是一个范德蒙德矩阵的转置，只不过生成元从 \((a_1\ \ a_2\ \cdots\ a_n)\) 变为了 \((a_1\ \cdots \ t \ \cdots \ a_n)\)。于是 \[ \det(A_k) = \left( \prod_{\substack{1 \le i < j \le n \\ i,j \neq k}} (a_j - a_i) \right) \cdot \left( \prod_{i=1}^{k-1} (t - a_i) \right) \cdot \left( \prod_{j=k+1}^{n} (a_j - t) \right) \] 将 \(\det(A)\) 和 \(\det(A_k)\) 的展开代入公式 \((1)\)，大部分的项都可以约分，最终剩下 \[ \large x_k = \frac{\prod\limits_{i=1, i \neq k}^{n} (t - a_i)}{\prod\limits_{i=1, i \neq k}^{n} (a_k - a_i)}\tag{2} \]
到这一步，计算每个 \(x_k\) 需要 \(O(n)\) 时间，于是我们已经可以 \(O(n^2)\) 地解决这个问题了。
接下来的优化需要引入一个辅助多项式，令
\[ F(x) = \prod_{i=1}^{n} (x - a_i) \]
那么，\((2)\) 的分子等价于 \(\dfrac{F(t)}{t-a_k}\)。
比较困难的是 \((2)\) 的分母部分，当你尝试用含 \(F(a_k)\) 的式子去描述这一部分，即 \(\dfrac{F(a_k)}{(a_i-a_i)}\)，分母为 \(0\) 显然就不可取了。
考虑 \(F(x)\) 的导数，依据乘积求导法则，有
\[ \frac{d}{dx} F(x) = \sum_{j=1}^{n} \left( \frac{d}{dx}(x-a_j) \cdot \prod_{i=1, i \neq j}^{n}(x-a_i) \right)=\sum_{j=1}^{n} \prod_{i=1, i \neq j}^{n} (x - a_i) \]
直观上来看是 \(n\) 项一堆乘积之和，当 \(x=a_k\) 时：
- \(j=k\) 的项等价于 \(\prod\limits_{i=1, i \neq k}^{n} (a_k - a_i)\)。
- \(j\neq k\) 的项一定会有 \(i=k\) 的时候，此时 \(a_k-a_i=0\)，整个项就为 \(0\)。
于是 \((2)\) 的分母就等价于 \(F'(a_k)\)。
总结一下，我们有 \[ x_k=\frac{F(t)}{(t-a_k)F'(a_k)} \] 其中 \(F(t)\) 可以将 \(t\) 代入 \(F(x)\) 线性算。
问题变为如何快速对所有 \(k\in [1,n]\) 求 \(F'(a_k)\)。
- \(F(x)\) 为 \(n\) 个一次多项式相乘，可以用分治 NTT 在 \(O(n\log^2n)\) 内构建。
- 知道了 \(F(x)\) 每一项的系数，\(F'(x)\) 可以线性构建。
- 求 \(F'(x)\) 在 \(x=a_1,a_2,\ldots,a_n\) 处的值，即【模板】多项式多点求值，同样为 \(O(n\log^2 n)\)。
E. 竞赛图
强连通 \(n(n\ge 3)\) 阶竞赛图一定存在一条哈密顿回路，因此 \(k\) 元环与大小为 \(k\) 的强连通分量等价。
特判 \(k=2\text{ or }k>n\) 答案为 \(0\)。问题转化为求包含至少一个大小为 \(k\) 的 SCC 的 \(n\) 个点的有标号竞赛图数量。
记号约定如下：
- \(f_i\)：大小为 \(i\) 的有标号强连通竞赛图数量。
- \(g_i\)：大小为 \(i\) 的有标号竞赛图数量。显然 \(g(i)=2^{\Large\frac{i(i-1)}{2}}\)。
- \(h_i\)：大小为 \(i\) 的所有 SCC 都 \(<k\) 的有标号竞赛图数量。
容斥，答案是 \(g_n-h_n\)。
如何求 \(h_n\)？首先，竞赛图缩点后会形成一条链，链首（即入度为 \(0\) 的点）向之后的所有点连边。计数时，我们从 \(n\) 个点里选出 \(i\in [1,k)\) 个点作为链首，这 \(i\) 个点组成 SCC 的方式就是 \(f_i\)，剩下 \(n-i\) 个点也需要满足 "所有 SCC 都 \(< k\)"，所以是 \(h_{n-i}\)，于是 \[ h_n=\sum_{i=1}^{k-1}\binom{n}{i}f_ih_{n-i}\tag{1} \] 先假设我们知道 \(f_i\)，来看我们如何算这个式子。
这是一个典型的使用 EGF（指数生成函数）计算的式子，但因为我是初学者，所以写一下推导过程。
将组合数展开，我们有 \[ h_n=\sum_{i=1}^{k-1}\frac{n!}{i!(n-i)!}f_ih_{n-i} \] 移项 \[ \frac{h_n}{n!}=\sum_{i=1}^{k-1}\left(\frac{f_i}{i!}\right)\left(\frac{h_{n-i}}{(n-i)!}\right) \] 这是一个卷积的形式。
令 \(H(x)=\sum\limits_{i=0}^{\infty}\dfrac{h_i}{i!}x^i\)，\(F_{<k}(x)={\sum\limits_{i=1}^{k-1}}\dfrac{f_i}{i!}x^i\)，则 \[ H(x)=1+F_{<k}(x)H(x) \] 其中 \(1\) 是因为 \(h_0=1\)，有 \([x^0]H(x)=1\)，这一项卷积里没有。
再移项，最终得到 \[ H(x)=\frac{1}{1-F_{<k}(x)}\tag{2} \] 只需要一次多项式求逆，之后 \(h_n=[x^n]H(x)\cdot n!\)。
接下来看如何求 \(f_i\)。
类似 \((1)\)，我们能得到一个 \(g_n\) 的递推式：从 \(n\) 个点里选出 \(i\in [1,n]\) 个点作为链首，这 \(i\) 个点组成 SCC 的方式就是 \(f_i\)，剩下 \(n-i\) 个点只用构成竞赛图就可以了，所以是 \(g_{n-i}\)，于是 \[ g_n=\sum_{i=1}^{n}\binom{n}{i}f_ig_{n-i} \] 可以发现，除了求和上界变成了 \(n\)，这简直和 \((1)\) 一毛一样。
这其实是 EGF 计数有标号的一般套路，求和上界变成 \(n\) 意味着我们可以用所有大小（也就是 \([1,n]\)）的强连通竞赛图构成整体。而在 \((1)\) 中我们只能使用大小 \(<k\) 的强连通竞赛图。
于是，类似 \((1)\to (2)\) 的过程，我们有 \[ G(x)=\frac{1}{1-F(x)} \] 这里 \(F(x)={\sum\limits_{i=1}^{\infty}}\dfrac{f_i}{i!}x^i\)，\(G(x)={\sum\limits_{i=0}^{\infty}}\dfrac{g_i}{i!}x^i\)。
移项 \[ F(x)=1-\frac{1}{G(x)} \] 最后 \(f_i=[x^i]F(x)\cdot i!\)。
时间复杂度 \(O(n\log n)\)。