题解 P7736 【[NOI2021] 路径交点】

· · 题解

很容易观察到题目考察的内容——交点数的奇偶性——只与两条路径的起点与终点有关系。

更进一步，不妨设这 n 条路径的起点是 1,2,...,n ，终点是 p_1,...,p_n （一个 1\thicksim n 的排列），那么这组路径的交点数的奇偶性就恰好是排列 p 的逆序对个数的奇偶性（或者直接称为排列 p 的奇偶性）。

而“偶排列比奇排列多多少个”这种问题我们再熟悉不过了：行列式！显然，如果 k=2 ，那么直接对着邻接矩阵求行列式就是答案。

如果 k 更大？一个简单的想法当然是，如果我求出 f_{ij} 表示从第一层第 i 个点到最后一层第 j 个点的路径条数（容易想到 f 的求法就是把每一层的邻接矩阵乘起来），然后对着这个矩阵做行列式不就完了？

然后你就去写了一发，并且过了看起来人畜无害的几组样例，就在你点击“提交”的一瞬间，突然一个激灵：“要求所有路径在中间不经过重复的顶点”这个条件怎么没用上？

你已经打算重新开始推式子了，再一抬头，“？？？怎么AC了？”（如果你没有不幸被卡常的话）

没错，直接这么做就是对的！接下来我不去讲LGV引理、柯西比内定理之类的东西（说实话我之前也没听说过LGV引理这个东西），我就从直观上描述：

如果我们允许道路在中间节点处交叉，会发生什么？

假设有两条路径，一条从第一层 x_i 连向最后一层 y_i ，另一条从第一层 x_j 连向最后一层 y_j 。两条路径在中间某层某个点 p 处相交。

那么对于任意包含这两条路径的一组路径，一定会有另一组路径与之对应：这两组路径的其他路径完全相同，只有这两条路径不一样——在第二组中，这两条路径在点 p 后互相交换，于是第一条路径从第一层 x_i 连向最后一层 y_j ，第二条路径从第一层 x_j 连向最后一层 p_i 。

容易看出这两组路径的交点数一定一奇一偶（容易证明下列引理：对于任意排列 p ，交换其中任意两个位置之后，排列的奇偶性一定改变）。

于是，我们很容易在所有含有相交路径的路径组之间建立一一配对的关系，从而所有这样的路径组对于答案的贡献会被全部抵消！

想明白这一点，这个题就极其简单了。

顺带一提， CF167E 跟这道题几乎是一模一样的思路和做法。今年NOI怎么这么多原题啊qwq

最后说一句，如果你不幸被卡常了，你可以注意到矩阵乘法过程中，每次乘的邻接矩阵的元素只有 0 和 1 ，因此你完全不需要每次做乘法就取一次模，而是每做完一次（甚至 4 次其实都可以）矩阵乘法之后整体取一次模。

如果还不行，你可以试试fread读入或者改变枚举顺序（从 ijk 改成 ikj ）之类的，不过这就挺玄学了，而且个人感觉加上取模优化就完全够用了。

复杂度显然是 O(n^3k) 。

代码如下：

#include<bits/stdc++.h>
char buf[100000],*buff = buf + 100000;
#define gc ((buff == buf + 100000 ? (fread(buf,1,100000,stdin),buff = buf) : 0),*(buff++))
#define li long long
#define pc putchar
using namespace std;
const int mo = 998244353;
inline int read(){
    int x = 0,c = gc;
    while(c < '0' || c > '9') c = gc;
    while(c >= '0' && c <= '9') x = x * 10 + c - '0',c = gc;
    return x;
}
inline void print(int x){
    if(x >= 10) print(x / 10);
    pc(x % 10 + '0');
}
int T,k,n[105],m[105];
struct mtx{
    li a[205][205];
    int x,y;
    inline li* operator [](int x){return a[x];}
    inline mtx(){x = y = 0;memset(a,0,sizeof(a));}
    inline void init(){x = y = 0;memset(a,0,sizeof(a));}
}a[105];
inline mtx operator * (mtx x,mtx y){
    assert(x.y == y.x);
    mtx as;as.x = x.x;as.y = y.y;
    li tmp;
    register int i,j,k;
    for(i = 1;i <= x.x;++i) for(k = 1;k <= x.y;++k){
        tmp = x[i][k];
        for(j = 1;j <= y.y;++j)
            as[i][j] += tmp * y[k][j];
    } 
    for(i = 1;i <= x.x;++i) for(j = 1;j <= y.y;++j) if(as[i][j] > 4e16l) as[i][j] %= mo;
    return as;
}
inline li ksm(li q,li w){
    li as = 1;
    while(w){
        if(w & 1) as = as * q % mo;
        q = q * q % mo;
        w >>= 1;
    }
    return as;
} 
inline li det(mtx x){
    assert(x.x == x.y);
    int n = x.x,i,j,k;
    for(i = 1;i <= n;++i) for(j = 1;j <= n;++j) x[i][j] %= mo;
    li tmp = 1;
    for(i = 1;i <= n;++i){
        if(!x[i][i]){
            for(j = i + 1;j <= n;++j) if(x[j][i]){
                tmp = (mo - tmp) % mo;
                for(k = i;k <= n;++k) swap(x[i][k],x[j][k]);
                break;
            }
        }
        if(!x[i][i]) return 0;
        (tmp *= x[i][i]) %= mo;
        li tp = ksm(x[i][i],mo - 2);
        for(j = i;j <= n;++j) (x[i][j] *= tp) %= mo;
        for(j = i + 1;j <= n;++j){
            tp = x[j][i];
            for(k = i + 1;k <= n;++k) (x[j][k] += mo - x[i][k] * tp % mo) %= mo;
            x[j][i] = 0;
        }
    }
    return tmp;
}
int main(){
    int i,j,u,v;
    T = read();
    while(T--){
        k = read();
        for(i = 1;i < k;++i) a[i].init();
        for(i = 1;i <= k;++i) n[i] = read(),a[i].x = a[i - 1].y = n[i];
        for(i = 1;i < k;++i) m[i] = read();
        for(i = 1;i < k;++i){
            for(j = 1;j <= m[i];++j){
                u = read();v = read();
                a[i][u][v] = 1;
            }
        }
        for(i = 2;i < k;++i) a[1] = a[1] * a[i];
        print(det(a[1]));pc('\n');
    }
    return 0;
}