线性代数与多项式

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

Example.1 随机数生成器

题意：

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


xxxxxxxxxx
1
ull seed = n;
2
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$ 。