自动搬运

查看原文

来自洛谷，原作者为

	nullqtr_pwp 我注意到有些人一直在做各种地方的cnoi题，但是并没有什么b用，可能是因为一直在舒适区里面舒服的卷，虐杀自己擅长的东西并获得成就感。

搬运于2025-08-24 22:44:51，当前版本为作者最后更新于2024-02-26 18:48:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

模拟赛不会 LGV 引理，喜提 $0\text{ pts}$。咋又是原题啊，被打爆了。

前置知识 - LGV 引理 以及 可能不需要知道的知识 - 行列式求值。

注意到本题要求路径不能有点相交，需要想到 LGV 引理。

LGV 引理：对于起点集合 $s_1,s_2,\cdots,s_k$，到终点集合 $t_1,t_2,\cdots,t_k$。记录一条路径的权值是上面所有边的边权乘积乘上符号（$(-1)^{\sigma (p)}$，为排列 $p_i$ 的奇偶性），令 $e(i,j)$ 为 $s_i$ 到 $t_j$ 上所有路径的权值和。这样构成的行列式值是 $s_i\to t_j$ 所有不相交路径组的权值和。不严谨的证明是，存在相交的路径会通过逆序对被消掉（对排列 $p$ 的影响就是交换 $i,j$，那么一定会导致排列的奇偶性改变）。

你发现权值中 $(-1)^{\sigma (p)}$ 很烦，但是本题是判定【是否存在】，不需要数数。所以可以考虑选定一个大质数 $P$（本题取 $P=998244353$ 即可），然后对每条边赋一个 $[0,P-1]$ 的随机边权。直接重新称呼一条路径的权值是 $\prod w_i$。

无解时，求出来的行列式值一定 $=0$，有解极大概率 $\ne 0$。首先跑一遍 $e_{u,v}$ 表示起点为 $u$，终点为 $v$ 的所有路径的权值（即随机边权的乘积 $\bmod \text{ }p$）的和，这是 LGV 引理需要的。

这时处理询问，对于一个区间 $[l,r]$，考虑 $f(l,r)=k$ 是否成立。把前面写出来的 $e_{i,v}$ 写成，一个 $k$ 维向量为 $V(i)=\lbrace e_{1,i},e_{2,i},\cdots e_{k,i}\rbrace$，那么 $f(l,r)=k$ 就要求 $V(l)\sim V(r)$ 组成的线性空间是否满秩。再推下去，若 $f(l,r)=x$ 就相当于可以选出来 $x$ 个起点，$x$ 个终点，拉出来这些可以搞出来一个行列式 $\ne 0$ 的 $x\times x$ 矩阵，也就是说考虑 $V(l)\sim V(r)$ 组成的极大线性无关组大小为 $x$，也就是线性空间的维数 / rank。

直接插线性基复杂度还是带 $n^2$ 的，考虑使用时间戳线性基，用来维护区间线性基。在记录基底的基础上，维护加入的时间戳，每次更新的时候也需要维护每个基底对应的时间戳，越晚越好。

注意到 $f(l,r)$ 对于一组定的 $l$ 单调，对于询问，就是计数 $f(l,r)=x$，注意到答案值域仅为 $k$，求出所有分界点即可。对 $r$ 进行扫描线，更新线性基。每次拉出来所有时间戳排序然后相邻两两做差即可。

时间复杂度 $O(nk^2+mk)$。

提交记录