[PA2021] Fiolki 2

· · 题解

模拟赛不会 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)。

提交记录