[luogu7736]路径交点

对于两条路径，注意到每一个交点都会改变两者的上下关系，因此两条路径交点的奇偶性，仅取决于两者的起点和终点是否改变了上下关系（改变即为奇数）

类似地，对于整个路径方案，令$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}\times 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\n",guess(n[1]));

72     }

73     return 0;

74 }

巴特西

[luogu7736]路径交点

最新文章

热门文章