代数

QOJ6190 Graph Problem

woodbury matrix identity

$$\left(A+UCV\right)^{-1}=A^{-1}-A^{-1}U\left(C^{-1}+VA^{-1}U\right)^{-1}VA^{-1}$$

题解

以下所有运算均在 $F_p$ 中进行。定义邻接随机矩阵 $T$，其中当且仅当存在边 $i\rightarrow j$ 或 $i=j$ 时 $T_{i,j}$ 为随机生成的权值，否则 $T_{i,j}=0$

则 $s$ 能到达 $t$ 当且仅当 $\left(I+T^1+T^{2}+\cdots\right)_{s,t}=\left(I-T\right)^{-1}_{s,t}\neq 0$

每次修改需要把 $\forall 1\le i\le n,1\le j\le k_1,i\neq p_j$，$T_{i,p_j}$ 改为 $0$，因为这样我们删掉了所有满足条件的点的入边，一定和原问题等价。

因此定义 $n\times k_1$ 的矩阵 $U$，$k_1\times k_1$ 的单位矩阵 $C$，$k_1\times n$ 的矩阵 $V$，满足:

$$ \begin{aligned}U_{i,j}&=\begin{cases}T_{i,p_j}& i\neq p_j\\0& \mathrm{otherwise}\end{cases}\\V_{i,j}&=\begin{cases}1& j= p_i\\0& \mathrm{otherwise}\end{cases}\end{aligned} $$

直接将 $A=I-T,U,C,V$ 带入上述恒等式

$A^{-1}$ 可以预处理。

然后，每次询问时，先计算出 $VA^{-1}U$:

由于 $V$ 只有 $V_{i,p_i}$ 有值，因此 $\left(VA^{-1}U\right)_{i,j}=\sum_{k\neq p_j}A^{-1}_{p_i,k}T_{k,p_j}$，可以预处理 $A^{-1}U$，对每个 $p_i=r,p_j=s$ 预处理，复杂度 $\mathcal{O}\left(n^3\right)$

因此可以花费 $\mathcal{O}\left(k_1^3\right)$ 时间计算出 $\left(C^{-1}+VA^{-1}U\right)^{-1}$

每次询问 $s,t$ 时，枚举 $l,r$ 计算 $\left(A^{-1}U\right)_{s,l}\times \left(C^{-1}+VA^{-1}U\right)^{-1}_{l,r}\times \left(VA^{-1}\right)_{r,t}$ 之和即可，单次复杂度 $\mathcal{O}\left(k_1^2\right)$

Submission Link

某神秘模拟赛（2023.06.14）

Tree

对于 $\sum a_i=n$ 的序列 $a$，必定存在一个 $k$，$k+\sum\left[a_i> k\right]=\left\lfloor\sqrt{2n}\right\rfloor+\mathcal{O}\left(1\right)$，令 $l=\left\lceil\sqrt{2n}\right\rceil$

$$ \sum_{i=1}^l\left(i+\sum_{j}\left[a_j> i\right]\right)\le\sum_i \left(a_i-1\right)+\left(l+1\right)l/2=2n+\mathcal{O}\left(\sqrt{n}\right) $$

因此可以知道，最小值 $\le \left\lfloor\sqrt{2n}\right\rfloor+\mathcal{O}\left(1\right)$