对于两条路径，注意到每一个交点都会改变两者的上下关系，因此两条路径交点的奇偶性，仅取决于两者的起点和终点是否改变了上下关系（改变即为奇数）
类似地，对于整个路径方案，令$p_{i}$为以第一层的$i$为起点的路径在第$K$层的终点，那么该方案的交点数的奇偶性，仅取决于$p_{i}$逆序对数（与逆序对数的奇偶性相同）
但注意到方案还有一个限制：不允许经过重复的点
但事实上，当经过了重复的点，显然将之后的两部分交换，恰好会改变$p_{i}$逆序对数的奇偶性
更准确的来说，考虑起点编号最小的两条有公共点的路径，将两者第一个公共点以后的部分交换，显然反过来另一条路径对应的也是原路径，即可以抵消
由此，令$A_{i,j}$表示起点为第一层的$i$且终点为第$K$层的$j$，显然答案即为$A$的行列式，可以$o(n^{3})$求出
关于如何求$A$，令$G_{i}$为第$i$层和第$i+1$层之间的邻接矩阵（大小为$n_{i} imes n_{i+1}$），显然$A=prod_{i=1}^{k-1}G_{i}$（其中乘法为矩阵乘法），可以$o(kn^{3})$求出
（单组数据）总复杂度为$o(kn^{3})$，可以通过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 205 4 #define mod 998244353 5 #define ll long long 6 int t,K,x,y,ans,n[N],m[N],a[N][N][N],b[N][N],c[N][N]; 7 int read(){ 8 int x=0; 9 char c=getchar(); 10 while ((c<'0')||(c>'9'))c=getchar(); 11 while ((c>='0')&&(c<='9')){ 12 x=x*10+c-'0'; 13 c=getchar(); 14 } 15 return x; 16 } 17 int qpow(int n,int m){ 18 int s=n,ans=1; 19 while (m){ 20 if (m&1)ans=(ll)ans*s%mod; 21 s=(ll)s*s%mod; 22 m>>=1; 23 } 24 return ans; 25 } 26 int guess(int n){ 27 int ans=1; 28 for(int i=1;i<=n;i++){ 29 int k=-1; 30 for(int j=i;j<=n;j++) 31 if (b[j][i]){ 32 k=j; 33 break; 34 } 35 if (k<0)return 0; 36 if (k!=i){ 37 ans=mod-ans; 38 for(int j=i;j<=n;j++)swap(b[i][j],b[k][j]); 39 } 40 ans=(ll)ans*b[i][i]%mod; 41 int s=qpow(b[i][i],mod-2); 42 for(int j=i;j<=n;j++)b[i][j]=(ll)b[i][j]*s%mod; 43 for(int j=i+1;j<=n;j++){ 44 int s=b[j][i]; 45 for(int k=i;k<=n;k++)b[j][k]=(b[j][k]-(ll)s*b[i][k]%mod+mod)%mod; 46 } 47 } 48 return ans; 49 } 50 int main(){ 51 t=read(); 52 while (t--){ 53 K=read(); 54 for(int i=1;i<=K;i++)n[i]=read(); 55 for(int i=1;i<K;i++)m[i]=read(); 56 memset(a,0,sizeof(a)); 57 for(int i=1;i<K;i++) 58 for(int j=1;j<=m[i];j++){ 59 x=read(),y=read(); 60 a[i][x][y]=1; 61 } 62 memset(b,0,sizeof(b)); 63 for(int i=1;i<=n[1];i++)b[i][i]=1; 64 for(int t=1;t<K;t++){ 65 memset(c,0,sizeof(c)); 66 for(int i=1;i<=n[1];i++) 67 for(int j=1;j<=n[t];j++) 68 for(int k=1;k<=n[t+1];k++)c[i][k]=(c[i][k]+(ll)b[i][j]*a[t][j][k])%mod; 69 memcpy(b,c,sizeof(b)); 70 } 71 printf("%d ",guess(n[1])); 72 } 73 return 0; 74 }