Note - 速通 NPC？有限域算术！-526互联

浅谈有限域在 OI 中的一些应用 (2023 国家集训队论文), 戚朗瑞.

$\textbf{Example 1.}$

给定一张有向图 $G=(V,E)$, $|V|=n$, $|E|=m$. 要求找到一条最长的简单路径. 保证最长路径长度 $k\ll n$.

$\textbf{Solution 1.}$

存在显然的 $\mathcal O\left(\binom{n}{k}\operatorname{poly}(n)\right)$ 的算法, 但我们更希望找到一种 $\mathcal O(T(k)\operatorname{poly}(n))$ 的算法. 不妨枚举路径长度 $k$, 转化为判定性问题.

构造多项式 这个算法策略大家或许已经很熟悉了: 钦定一个阈值 $w$, 构造 $\mathbb{GF}(2^w)$ 中的多项式, 使得 "存在长度为 $k$ 的简单路径 $\Leftrightarrow$ 多项式非 $0$" 的置信度足够高.

首先, 我们给路径随机赋权. 设 $X_{n\times n}$ 是一个在 $\mathbb{GF}(2^w)$ 中随机生成的 $n^2$ 个数组成的矩阵, 对于路径 $P=(v_1,v_2,\cdots,v_k)$, 令其权值为 $\prod_{i=1}^{k-1}X_{v_iv_{i+1}}$.

当然, 接下来的难点在于剔除掉其中的非简单路径. 剔除的方法就需要利用域特征为 $2$ 的性质: $a+a=0$. 我们可以尝试使所有非简单路径对总和的贡献次数是偶数, 这样就能将它们的贡献剔除了. 同时, 利用环的性质, 若 $P$ 有环, 就会有偶数种绕圈的方式, 也即将 $P$ 中的边重排构成路径的方式是偶数.我们再随机生成一个矩阵 $Y_{n\times k}$ 来描述这种构造. 对路径 $P$, 我们将它的权值乘上

\[\sum_{\sigma\in S_n}\prod_{i=1}^kY_{v_i\sigma_i}, \]

其中 $S_n$ 是全局 $n$ 阶置换集合. 可以感受到, 当 $v_i$ 两两不同时, 上式 "很大概率" 非 $0$; 而当 $v_i=v_j~(i\neq j)$ 时, 上式显然为 $0$.

最后, 我们就是要求出

\[P(X,Y)=\sum_{|P|=k}\prod_{i=1}^{k-1}X_{v_iv_{i+1}}\sum_{\sigma\in S_k}\prod_{i=1}^kY_{v_i\sigma_i}. \]

构造过程到此为止, 接下来我们只需要计算这个结果就行.

求解多项式 比较自然的想法: 对 $\sigma$ 状压 DP. 令 $f(u,S)$ 表示 $v_{|S|}=u$ 且 $\sigma$ 取过 $S$ 中的值时, 上式的和. 转移枚举 $u$ 的邻接点和 $\sigma_{|S|+1}$ 的取值即可. 转移次数为 $\mathcal O(2^kkm)$, 我们一般取 $w\le\omega$ 更方便地使用位运算, 最终复杂度为 $\mathcal O(2^kkmw)$.

当然, 我们还能把 $\mathcal O(2^kn)$ 的空间复杂度优化到线性. 利用容斥处理集合状态:

\[\begin{aligned} \mathcal Y(P) &= \sum_{\sigma\in S_n}\prod_{i=1}^kY_{v_i\sigma_i}\\ &= \sum_{S\subseteq[1:k]}(-1)^{k-|S|}\prod_{i=1}^k\sum_{\sigma_i\in S}Y_{v_i\sigma_i}\\ &= \sum_{S\subseteq[1:k]}\prod_{i=1}^k\sum_{\sigma_i\in S}Y_{v_i\sigma_i}. \end{aligned} \]

这样 $S$ 就能在外部枚举了.

正确性分析 接下来的问题是考察算法正确性. 本质上, 我们构造出了以 $x_{ij},y_{ij}$ 为变元的判别式 $P(X,Y)$, 并考察是否有 $P(X,Y)=0$. 当随机判断错误时, 我们相当于找到了一组 $P(X,Y)$ 的根. 此时, 有 Schwartz-Zippel 引理:

$\textbf{Lemma (Schwartz-Zippel).}$ 若多项式 $P\neq0$, 则 $\Pr(P(r_1,r_2,\cdots,r_n)=0)\le d/|F|$, 其中 $d=\deg P$, $F$ 为系数域.

$\textbf{Proof.}$ 对 $n$ 归纳. 当 $n=1$ 时显然成立. 设 $n=k$ 时成立, 现对 $n=k+1$ 归纳:

设 $P$ 中 $x_1$ 的最高次为 $t$, 令 $P=x_1^tQ(x_2,x_3,\cdots,x_{k+1})+R(x_1,x_2,\cdots,x_{k+1})$. 那么

\[\begin{aligned} \Pr(P=0) &= \Pr(P=0\mid Q=0)\Pr(Q=0)+\Pr(P=0\mid Q\neq 0)\Pr(Q\neq 0)\\ &\le \Pr(Q=0)+\Pr(P=0\mid Q\neq 0)\\ &\le \Pr(Q=0)+\Pr(P(x_1{\color{red}{;}}~x_2,x_3,\cdots,x_{k+1})=0)\\ &\le (d-t)/|F|+t/|F|\\ &= d/|F|. \end{aligned} \]

$\square$

运用引理, 该算法的正确率为 $\frac{2k-1}{2^w}$, $w$ 取一个不算大的值就能得到良好的效果.

构造方案 钦定可行起点集合, 迭代 $k$ 次算法即可. 复杂度不变.

$\textbf{Example 2.}$

给定一个含有 $n$ 个点 $m$ 条边的无向图 $G=(V,E)$, 点 $u$ 有颜色 $c_u$. 你需要选出一个点集 $V_0$, 记其在 $G$ 中的导出子图为 $G_0$, 则其满足 $G_0$ 连通且颜色 $i$ 在 $V_0$ 中的出现次数 $\le m_i$. 保证 $m=\sum_im_i\ll n=|V|$.

$\textbf{Solution 2.}$

如同上一题, 我们先把原问题转化为判定性问题. 枚举点集的大小 $k$, 检查是否存在可行的导出子图.

构造多项式 点集 $V$ 合法有两个判断要素: 一是连通, 二是颜色出现次数满足限制. 我们的构造性算法更容易描述 "存在某种要素组合", 分别考虑对二者的描述:

对于连通, 可以通过 "存在生成树" 来描述. 设 $X_{n\times n}$ 是同上题的随机矩阵, 则对于枚举的有根生成树树边集合 $E_T$, 其贡献

\[\prod_{\lang u,v\rang\in E_T}X_{uv}. \]

对于颜色出现次数限制, 可以通过 "存在一种对点集内结点编号的方法, 使得同色结点编号不同". 这里, 结点 $u$ 的编号是 $[1,m_{c_u}]$ 内的整数. 而 "编号不同" 就可以使用上题的构造策略了. 我们生成 $Y_{n\times m}$ 用于编号, $Z_{m\times m}^{(i)}$ 用于对颜色 $i$ 的重复编号进行抵消, 那么这部分的贡献为

\[\sum_{\varphi}\prod_{u\in V_T}Y_{u\varphi_u}\sum_{\sigma}\prod_{v\in V_T}Z_{\varphi_v\sigma_v}^{(i)}. \]

其中 $\varphi$ 枚举编号方法, $\sigma$ 枚举对结点的编号排列.

那么, 一颗固定有根树 $T=(V_T,E_T)$ 的贡献为

\[\prod_{\lang u,v\rang\in E_T}X_{uv}\sum_{\varphi}\prod_{u\in V_T}Y_{u\varphi_u}\sum_{\sigma}\prod_{v\in V_T}Z^{(i)}_{\varphi_v\sigma_v}. \]

求解多项式 同上一题一样, 我们先枚举 $\sigma$ 的实际值域 $S$ 并固定. 接下来需要计算的是:

\[\prod_{\lang u,v\rang\in E_T}X_{uv}\prod_{u\in T}\left(\sum_{\varphi}Y_{u\varphi_u}\sum_{\sigma,\sigma_i\in S}Z^{(i)}_{\varphi_u\sigma_u}\right)=\prod_{\lang u,v\rang\in E_T}X_{uv}\prod_{u\in T}W_u. \]

当然, 特征为 $2$ 的有限域下, 我们并不需要用诸如状压的手段保证 $T$ 中结点两两不同. 直接令 $f(r,s)$ 表示以 $r$ 为根, 大小为 $s$ 的有根树的贡献和, 枚举 $r$ 的一个孩子转移就行. 最终复杂度 $\mathcal O(2^mm^2|E|w)$.

正确性分析 和上面一样的嘛.

构造方案 找到有答案的根 $r$, 不断加入其邻接边直到出现答案, 此后将这条边的端点与根合并, 更新$\{m\}$ 集合, 迭代即可. 复杂度不变.

three_level_npc_inverter