主要记录了最近考试遇到的一些(可能)比较有用的 trick / 结论,不定时更新.
系数模合数的截断多项式行列式计算
矩阵 $A$ 的每个元素是一个次数小于 $k$ 的关于 $x$ 的多项式,在 ${\rm mod}\ x^k$ 意义下计算行列式,系数对某个合数取模.
构造以二元多项式 $f(x,y)$ 为元素的矩阵 $B=I+y(A-I)$ ,计算出 $B$ 的行列式,代入 $y=1$ 即得 $A$ 的行列式.
矩阵 $B$ 只有对角线上的元素有常数项 $1$ ,并且在高斯消元的过程中这个性质不会被破坏.
常数项为 $1$ 保证了每次都可以求出逆元,只需要实现二元多项式的加法,乘法,即可完成高斯消元,求出行列式.
一元多项式方程实数根求数值解
给出一个关于 $x$ 的 $n$ 次多项式 $f(x)$ ,求出它的所有实数根,用近似值表示.
考虑求出 $f(x)$ 的所有驻点,相邻两个驻点之间 $f(x)$ 是单调的,最多有一个解,可以在每个区间内二分尝试求解.
根还有可能位于最小的驻点左侧或最大的驻点右侧,找一个合适的上下界,在对应的区间内同样二分求解.
$f(x)$ 的所有驻点就是 $f’(x)$ 的所有零点,可以变成子任务递归求解,递归到多项式次数 $=1$ 时可以直接算出解.
循环矩阵的行列式计算
若 $n$ 阶方阵 $\mathbf C$ 满足如下形式,则称它为循环矩阵:
$$
\mathbf C=
\begin{bmatrix}
a_0& a_1& a_2& \cdots& a_{n-2}& a_{n-1} \\
a_{n-1}& a_0& a_1& \cdots& a_{n-3}& a_{n-2}\\
a_{n-2}& a_{n-1}& a_0& \cdots& a_{n-4}& a_{n-3}\\
\vdots& \vdots& \vdots& \ddots& \vdots& \vdots\\
a_2& a_3& a_4& \cdots& a_0& a_1\\
a_1& a_2& a_3& \cdots& a_{n-1}& a_0
\end{bmatrix}
$$
记 $\displaystyle A(x)=\sum_{i=0}^{n-1}a_i x^i,\omega_n$ 为 $n$ 次单位根,则 $\displaystyle \det(\mathbf C)=\prod_{k=0}^{n-1} A(\omega_n^k)$ .对向量 $a$ 做一次 DFT 即可求出每个 $A(\omega_n^k)$ .
由于我不会证, 此处证明略去.
前缀和优化数列递推
给定一个 $m$ 次多项式 $F(x)$ ,有递推式 $f_0=1,f_i=\sum_{j=0}^{i-1} f_j\cdot F(i-j)$ ,需要求出 $f_1,f_2,\dots, f_n$ .
系数对 $10^9+7$ 取模, $n$ 较大, $m$ 较小,要求时间复杂度做到 $O(nm)$ .
设多项式 $G_i(x)=\sum_{j< i} f_j\cdot F(x-j)$ ,那么 $f_i=G_i(i)$ .
这里涉及到多项式的平移,考虑用点值维护 $G(x)$ ,即维护 $G(0),G(1),\dots G(m)$ 的值.
由于 $G_i(x)=G_{i-1}(x)+ f_{i-1}\cdot F(x-i+1)$ ,预处理 $F(-n+1)\sim F(n+m-1)$ 这 $n+m$ 个点值就足够了.
每次询问 $G(x)$ 的值时使用拉格朗日插值,
$$
G(x)=\sum_{i=0}^m G(i)\cdot \prod_{j\neq i} \frac{x-j}{i-j}
$$
可以先算出 $\prod (x-j)$ ,枚举 $i$ 时将它除掉 $(x-i)$ ,单次就可以 $O(m)$ 计算 $G(x)$ 了,总时间复杂度 $O(nm)$ .
拓展性比较强,可以钦定某些位置转移,比如给每个位置安排一个 $col_i$ ,规定只有 $col_j\neq col_i$ 的 $f_j$ 才能转移.
那么我们维护原来的 $G$ 和每种 $col$ 的 $G$ ,询问时将 $col$ 相同部分的贡献减去即可.
把 $F(x)$ 换成某个线性递推的第 $x$ 项的值仍是可做的,算出通项公式后相似地维护前缀和即可.
一类线性递推数列的计算
给定常量 $a,b$ ,有递推数列 $f_0=1,f_i=af_{i-1}+[i\ge k]bf_{i-k}$ ,求 $f_n$ .
可以看成要上 $n$ 步阶梯,每次上 $1$ 步的方案数是 $a$ ,每次上 $k$ 步的方案数是 $b$ ,问上 $n$ 步的方案数,
枚举有 $i$ 次上了 $k$ 步,可得 $f_n=\sum_{i\ge 0,ik\le n}a^{n-ik}b^i\binom{n-ik+i}{i}$ ,时间复杂度 $O(\frac n k)$ .
但需要先花 $O(n)$ 的时间去预处理阶乘及其逆元,只有在多次询问,或转移系数是多项式等情况下才比较有用.
在线 “莫队”
也不知道这个东西还能不能算莫队,不过最基础的思想和莫队是一样的,姑且叫在线 “莫队” 好了.
这里假定从 $[L,R]$ 转移到 $[L,R+1],[L,R-1],[L+1,R],[L-1,R]$ 时更新信息的代价都是 $O(1)$ 的.
莫队算法需要先将所有询问离线下来,经过适当排序后处理,若强制在线,可以用这个 trick 进行处理:
考虑莫队的本质,可以看作是将一个询问 $[l,r]$ 看作二维平面上的一个点,从一个区间转移到另一个区间的代价是对应的两个点之间的 Manhattan 距离,需要找一条总代价能接受的路径,经过每个点至少一次.
莫队就是给这些点按照某种方式排了序,使得路径总代价是 $O(n\sqrt m)$ 的.
而现在强制在线,每次必须走到一个给定的点,一个简单的想法是在平面上找一些关键点,预处理它们的信息,询问时找一个 Manhattan 距离最小的关键点转移过去就行了.
均匀撒点,在所有 $L=i\cdot S,R=j\cdot S$ 的 $(L,R)$ 都设立一个关键点,并预处理每个关键点对应区间信息.
共 ${n^2}/{S^2}$ 个关键点,预处理复杂度 $O({n^3}/{S^2})$ ,每次询问到最近关键点 Manhattan 距离 $O(S)$ ,复杂度 $O(mS)$ .
假定 $n,m$ 同阶,则取 $S=n^{\frac 2 3}$ 可得到总时间复杂度与空间复杂度均为 $O(n^{\frac 5 3})$ .
这个东西也可以方便地支持单点修改,每次将所有区间包含它的关键点都 $O(1)$ 更新一遍,总复杂度仍为 $O(n^{\frac 5 3})$ .
在较小 NTT 模数下的多项式多点求值
Codechef POLYEVAL Evaulate the Polynomial
给一个 $n$ 次多项式 $f(x)=\sum_{i=0}^n a_i x^i$ ,在模 $P=3\times 2^{18}+1$ 意义下做多点求值, $n\le 2.5\times 10^5$ .
直接冲一个 $E 多点求值可以通过.
取 $P-1$ 次单位根 $\omega_{P-1}\equiv g$ ,其中 $g$ 为 $P$ 的任意一个原根.
用 Bluestein 对向量 $a$ 做一次模长为 $P-1$ 的 DFT 即可求出所有的 $f(g^i)$ ,也就得到了 $f(1),f(2),\dots f(P-1)$ . 再特判 $f(0)=a_0$ 即可,时间复杂度 $O(P\log P)$ .
竞赛图
$n$ 个点的竞赛图是一张有向图,满足每两个点之间都恰有一条边,由一者指向另外一者.
三元环
竞赛图要么是一张 DAG, 要么存在至少一个三元环.
若是 DAG, 则对于两个不同的点 $u,v$ ,$u$ 能到 $v$ 与 $v$ 能到 $u$ ,恰有一个是成立的.
竞赛图的三元环数目为 $\binom n 3-\sum_{i=1}^n \binom{outdeg(i)}2$ ,其中 $outdeg(i)$ 表示 $i$ 的出度.
哈密尔顿路径
$x$ 能成为哈密尔顿路径起点的充要条件是从 $x$ 出发能到达所有其他的 $n-1$ 个点,必要性显然,充分性可以归纳证明.
更一般地,若从 $x$ 出发能到达恰好 $k$ 个点(包括 $x$ 自己),则从 $x$ 出发的最长简单路径经过的点数恰好也为 $k$ .
从这个结论出发,不难分析出,竞赛图中必定存在至少一条哈密尔顿路径.
哈密尔顿回路
竞赛图存在一条哈密尔顿回路的充要条件是这个竞赛图强连通,必要性显然,充分性可以归纳证明.