线性代数与多项式.md

线性代数与多项式

讲师：PinkRabbit 时间：20210629 地点：福建师范大学附属中学

Example.1 随机数生成器

题意：

给出一个随机数生成器（如下）

ull seed = n;
int get_rand() { seed ^= seed << 13, seed ^= seed >> 17, seed ^= seed << 5; return seed; }

$T$ 组询问，每组询问给定种子和 $n$，询问第 $n$ 次生成的值

$T≤2×10^5$, $n≤10^{18}$, $2s$, $256MB$

题解：

这个过程可以用一个 $\bmod 2$ 的矩阵乘法来表示。设 $n$ 的二进制表示为 $\vec{v}$，则答案可以表示为： $$ A^n\times\vec{v} $$ 如果直接做矩阵快速幂，则复杂度是 $q\omega^3\log n$，过个寂寞！

这时采用经典方法：讲 $A^{2^{1\sim \omega}}$ 预处理出来，那么每次乘法时只需要进行矩阵乘向量即可，这个乘法是 $O(\omega^2)$ 的；结合位运算可以优化到 $O(\omega)$。但是总的复杂度还是 $\omega^2q$ 的，过不去。

考虑更大力的优化，我们直接抛弃二进制，使用 256 进制的这个做法，则复杂度将为 $(\omega^2\cdot256+\omega q)\cdot\log_{256}n$。

Example.2 城市道路问题

题意：

$n$ 个城市，第 $i$ 个城市有 $2k$ 个点权 ($a_{i, 1}$, $a_{i, 2}$, …, $a_{i, k}$;$b_{i, 1}$, $b_{i, 2}$, …, $b_{i, k}$)

从城市 $u$ 直接到 $v$ 一共有 $\sum_{i=1}^ka_{u, i} b_{v, i} $ 种方案，$u$ 可以等于 $v$。

$m$ 组询问，询问城市 $u$ 在 $d$ 步内到达城市 $v$ 的方案数，对 $10^9+7$ 取模

$n≤1000$, $d<2^{31}$，$k≤20$, $m≤50$ 或 $k=1$, $m=100$。1s, 128MB

题解：

首先对于每种边建一个虚点（也可以理解为 $A_{k,n}\times B_{n,k}=C_{k,k}$），建立虚点到虚点的状态转移矩阵 $C$。问题转化为： $$ \left(\sum_{i=0}^d{C^i}\right)\times \vec{v} $$ 左边的这个东西我们可以通过矩阵求逆轻松得到（$\frac{I-C^{d+1}}{I-C}$）；如果逆不存在怎么办？

考虑大力倍增： $$ \sum_{i=0}^{2t-1}C^i=\left(\sum_{i=0}^{t-1}C^i\right)\times\left(I+C^{t}\right) $$

Example.3

题意：

一张 $n=2^m$ 个点的有向完全图。

任意两点 $i, j$ 之间的有向边 $i\rightarrow j$ 的边权是 $w_{(i-j) \bmod n}$。

求这张图的所有生成内向森林的边权乘积之和。$m≤20$, 模 $998244353。

题解：

考虑将每个点均连向一个虚点，这样内向森林个数就是这张图的内向树个数；同时，由于基尔霍夫矩阵的这一阶要去掉，那不妨就不管这个矩阵了，直接想办法求这张图的基尔霍夫矩阵的行列式即可。

注意到，这个矩阵是一个循环矩阵；而循环矩阵的行列式可以表示为： $$ \prod_{k=0}^nf(\omega_n^k) $$ 其中 $f=\sum_{i=1}^nA_{1,i}\cdot x^i$。证明：

设矩阵 $V={v_{i,j}=\omega_n^{ij}}$，有： $$ (AV){i,j}=\sum{k=1}^n A_{i,k}\cdot V_{k,j}=\sum_{k=1}^n A_{1,k-i+1}\cdot\omega_n^{kj}=\omega_n^{ij}\cdot f(\omega_n^j) $$ 每一列都同时乘以一个数，则有： $$ det(AV)=det(V)\cdot\prod_{i=1}^nf(\omega_n^i) $$ 所以有：$det(A) = \prod_{i=1}^nf(\omega_n^i)$。

如何求 $f$ 的这个乘积呢？先 $NTT$ 一下，然后把每个位置全部乘起来就行了。

Example.4

题意：

给定一个 $1$ 到 $n$ 的排列 $q$ 和一个序列 $h$。定义一个 $1$ 到 $n$ 的排列 $p$ 的值为 $$ v(p)=\sum_{i=1}^n\sum_{j=i+1}^n{[p_i>p_j]+[p_i+h_i\ge q_j]} $$ 求有多少个 $1$ 到 $n$ 的排列 $p$ 使得 $v(p)$ 为偶数。对 $998244353$ 取模，$n≤300$。

题解：

显然答案为： $$ \frac {n!+\sum_P(-1)^{v(P)}}2 $$ 考虑前面那个艾弗森括号，它的形式很接近行列式中的 $(-1)^{\operatorname{sign}(P)}$ 项；枚举排列的任务也由行列式完成了，剩下的是如何解决后面的那个艾弗森括号。我们考虑构造下列矩阵： $$ A_{i,j}=(-1)^{\sum_{j=1}^n[i+h_i>q_j]} $$ 显然 $det(A)=\sum_P(-1)^{v(P)}$。

Example.5 九个太阳

题意：

给定 $n$, $K$, 满足 $K$ 是 $2$ 的幂，求 $$ \sum_{i=1}^{+\infty}\begin{pmatrix}n\iK\end{pmatrix} $$ 对 $998244353$ 取模。$1≤n≤10^{15}$, $1≤K≤2^{20}$。

题解：

倍数 类型的问题可以考虑单位根反演： $$ [d|n]=\frac 1d\sum_{i=0}^{d-1}\omega_d^{in} $$ 于是这题的式子可以写为： $$ \frac 1K\sum_{i=1}^{+\infty}{\left(\sum_{j=0}^{K-1}\omega_K^{ji}\right)\cdot\begin{pmatrix}n\i\end{pmatrix}}=\frac 1K\sum_{j=0}^{K-1}\sum_{i=1}^{+\infty}\omega_K^{ji}\cdot\begin{pmatrix}n\i\end{pmatrix}=\frac 1K\sum_{j=0}^{K-1}(\omega_K^j+1)^n $$ 搞定。一般来说，单位根相关题目都有一个 $2$ 的次幂和 $998244353$。

Example.6 复读机

题意：

在长度为 $n$ 的序列中填入 $1, 2, \cdots, k$, 使得它们出现次数均为 $d$ 的倍数。

求方案数，模 $19491001$。

$d≤3$, $k≤5×10^5$。当 $d=3$ 时 $k≤1000$。1s, 512MB

题解：

显然有： $$ ans=n!\cdot[x^n]\left(\sum_{i=0}^{+\infty}\frac {x^{id}}{(id)!}\right)^k $$ 当 $d=1$ 时： $$ ans=n!\cdot[x^n]e^{kx}=k^n $$ 当 $d=2$ 时： $$ ans=n!\cdot[x^n]\left(\frac {e^x+e^{-x}}2\right)^k=\frac 1{2^k}\cdot n!\cdot[x^n] \sum_{i=0}^k\begin{pmatrix}k\2\end{pmatrix}\cdot e^{(2i-k)x} $$ 当 $d=3$ 时： $$ ans=n!\cdot[n!]\left(\frac {e^x+e^{\omega_3^1x}+e^{\omega_3^2x}}3\right)^k $$ 对于隔 $k$ 个 $0$ 一个 $1$ 的这种序列的 EGF 通常可以使用单位根来表示。

Example.7 XLkxc

题意：

求 $\sum_{i=0}^n\sum_{j=1}^{a+id}\sum_{l=1}^j l^k$，模 $1234567891$。

$k≤3000$, $1<a, n, d<1234567891$。1s, 512MB

题解：

$\sum_{l=1}^j l^k$ 是关于 $j$ 的 $k+1$ 次式。

$\sum_{j=1}^{a+id}\sum_{l=1}^j l^k$ 是关于 $a+id$ 的 $k+2$ 次式（即关于 $i$ 的）。

原式是关于 $n$ 的 $k+3$ 次式。直接插值插出来就行了。

Example.8 斗主地

题意：

有 $n$ 张牌，从上到下标号为 $1, 2, …, n$, 标号为 $i$ 的牌分数为 $i^{type}$ 进行 $m$ 轮洗牌，第 $i$ 轮拿出顶上 $A_i$ 张牌，从而分成两堆。

洗牌的过程是，若两堆各有 $X, Y$ 张牌，则分别有 $\frac X{X+Y},\frac Y{X+Y}$ 概率拿出这堆的第一张牌作为洗牌后的第一张，然后递归确定余下的部分。

求 $m$ 轮洗牌后各位置上的牌的期望分数（进行 $Q$ 次询问）

$3≤n≤10^7$, $1≤m,Q≤5×10^5$, $type∈{1, 2}$。

题解：

考虑这个发牌方式到底代表了什么？均匀分配！即每一种方案的概率是相等的。我们来证明一下：

设 $X$ 这一组分别是在 $p_{1\sim X}$ 处取得，那么显然这个方案的可能性为： $$ \prod_{i=1}^x\left(\prod_{j=p_{i-1}+1}^{p_i-1}\frac{Y+i-j}{N-p_i+1}\right)\cdot\frac{X-i+1}{N-p_i+1} $$ 考虑在最.9后把项数补齐： $$ \left(\prod_{i=1}^x\left(\prod_{j=p_{i-1}+1}^{p_i-1}\frac{Y+i-j}{N-p_i+1}\right)\cdot\frac{X-i+1}{N-p_i+1}\right)\cdot\prod_{j=p_X+1}^N\frac{N-i+1}{N-i+1} $$ 一通变换求和顺序得： $$ \left(\prod_{i=1}^X X-i+1\right)\cdot \left(\prod_{i=1}^N N-i+1\right)\cdot \left(\prod_{i=1}^X\left(\prod_{j=p_{i-1}+1}^{p_i-1}Y+i-j\right)\times\prod_{p_X=1}^N Y+X-i\right) $$ 第一个括号是 $X!$，第二个括号是 $\frac 1{n!}$，第三个括号刚好遍历了每一个第二堆中的数的剩余量，因此是 $Y!$。

综上每一种情况的概率都是 $\begin{pmatrix}n\2\end{pmatrix}^{-1}$。

既然是均等的，那么容易写出 $i\rightarrow j$ 的转移系数就是 $\begin{pmatrix}j-i\i-1\end{pmatrix}\cdot\begin{pmatrix}n-j\X-i\end{pmatrix}\cdot\begin{pmatrix}n\X\end{pmatrix}^{-1}$。

如果一列的值是关于其位置的 $type$ 次函数，那么经过一次线性变换后，新的一列也是 $type$ 次函数；因此做前三行，把答案插值插出来就行。

Example.9 Arcs on a Circle

gugugu

Example.10

题意：

平面直角坐标系上有一个醉汉位于原点。

每一步，他分别有 $p_1$,$p_2$,$p_3$,$p_4$ 概率向西、南、东、北方向走一个单位长度。

移动 $n$ 步，求经过的点数期望值（经过多次只算一次），保留三位小数。$n≤50$, 2s, 256MB

题解：

关于第一次经过，有一个非常神仙的做法。设 $f_{t,i,j}$ 表示 $t$ 时刻位于 $(i,j)$ 的概率，这是可以 $O(n^3)$ 得到的。

设 $G_{i,j}(x)=\sum_{t=0}^n f_{t,i,j}\cdot x^t$，$F(x)=\sum_{t=0}^n F_{t,0,0}\cdot x^t$，$Q_{i,j}(x)$ 表示 $(i,j)$ 点第一次经过关于时间的概率生成函数。显然： $$ Q_{i,j}\times F = G_{i,j} $$ 将 $F$ 求逆然后求个前缀和，精细实现一下就是 $O(n^3)$ 的。

Example.11 机器人

题意：

$n$ 个整数 $h_1,h_2,…, h_n$, $h_i$ 在一个区间 $[A_i, B_i]$ 中选取。

比较两个元素的大小，如果大小相同，认为较前的更小。从每个位置出发分别进行向左、向右两次试验。一次试验是往该方向找到最长的一段位置，使得它们的值都小于出发位置

求有多少种方案使得，每个位置的两次试验得到长度差不超过 $2$。

答案模 $10^9+7$，$n≤300$, $A_i≤B_i≤10^9$。3s, 512MB

题解：

试验的长度差不超过二，意味着如果建出笛卡尔树，那么每个点必然在其区间的中间三个位置之一！因此我们向下递归计算，这本身的复杂度不是很大。

考虑计算过程中维护一个数组 $f_i$ 表示当前点的子树对应的区间，选出的数的最大值是 $i$ 的方案数，于是转移方程： $$ f_{u,i}=\left(\sum_{j=1}^{i-1}f_{l,j}\right)\cdot\left(\sum_{j=1}^if_{r,j}\right),j\in[a_u,b_u] $$ 那么我们要维护这样一个 $dp$ 数组，能够支持左移、点积、前缀和。那么这个就是多项式了，计算点值然后插值来维护。但是注意，一定要分成多段多项式，因为整个连在一起就不是多项式了。

注意，这里的维护嘛，其实可以直接维护一些点值，然后一段中有效点值的个数即将少于其次数时，我再插值插一个出来备用即可，复杂度不大。

Example.12

题意：

设有一随机数生成器能生成 $0$ 到 $k$ 的整数，其中生成 $i$ 的概率为 $p_i$, $p_0≠0$。

用该生成器独立生成 $n$ 个随机变量，设它们的和为 $s$。

求 $s$ 取得 $0, 1, \cdots, m$ 的概率各为多少。

模 $10^9+7$，$1≤n<10^9+7$, $1≤km≤10^7$,1s, 256MB。

题解：

换句话说，题目是求： $$ [x^{1\sim m}]\left(\sum_{i=0}^k p_ix^i\right)^n $$ 我们拓展为更一般的形式： $$ [x^{1\sim m}]\left(F(x)\right)^n $$ 设 $G(x)=F^n(x)$，两边求导： $$ G'(x)=n\cdot F^{n-1}(x)\cdot F'(x) $$ 代入 $F^{n-1}(x)=\frac {G(x)}{F(x)}$ 得： $$ G'(x)\times F(x)=n\cdot G(x)\times F'(x) $$ 提取 $[x^s]$ 系数得： $$ \sum_{i=0}^s p_{s-i}\cdot g_{i+1}\cdot(i+1)=n\sum_{i=0}^sg_{s-i}\cdot f_{i+1}\cdot(i+1) $$ 这样就可以 $O(km)$ 递推了。事实上，这个方法非常强大，甚至可以解决 $n$ 不是整数得情况。

Example.13

题意：

给定一张 $n$ 个点的有向图，给定两点 $s, t$。

杏仁子图：$s→t$ 间（除两端外）点不交的若干条链组成的子图

$q$ 次询问，每次强制 $s$ 点与 $u$ 点相连，求有多少个杏仁子图

$n≤22$, 2s, 1GB

题解：

实际上询问只有 $22$ 种……

设 $f_{u,S}$ 表示从 $u$ 出发到 $t$ 经过点集 $S$ 的方案数，这个可以 $O(n^22^n)$ 轻松得到；从而可以处理出 $g_{u,S}$ 表示第一步走了 $u$ 的到 $t$ 的路径个数。

把所有的 $g$ 拼起来作为集合幂级数 $Q$，那么我们实际上要求的就是： $$ \sum_{i=0}^n \frac {Q^i}{i!}=\exp(Q) $$ （上述为不交并卷积，$\exp$ 是因为要除掉具体每部分是从哪个 $G$ 来的）

我们把集合幂级数当作一个 $n$ 次的形式幂级数，但是每一项的系数是一个集合幂级数（服从 $or$ 卷积）；原有的每个集合仅仅加到 $|S|$ 的那个位置上。我们称这个多项式叫占位多项式。

我们发现，子集卷积等价于占位多项式的普通卷积（其中系数按照 $or$ 卷积），尽管反复乘法会多一些无用的项，但是因为是真的无用，所以就压根不用管）。

进而，$\exp$ 也可以用这种占位多项式的普通卷积来定义；而普通卷积可以通过 $(e^{F})'=F'(e^F)$' 从而递推得到。复杂度就是 $O(n^2)$ 的（内层还有一个 $O(2^n）$.

处理出了 $\exp(Q)$，我们就可以考虑怎么统计答案。我们把 $\exp(Q)$ 再进行一次 FWT，处理出子集前缀和；对于每个 $u$ 直接枚举 $S$，用 $g_{u,S}\times H_{U-S}$ 统计进答案（$H$ 是 FWT 的结果）。复杂度 $n2^n$。

总复杂度 $n^22^n$。