自动搬运

查看原文

来自洛谷，原作者为

	SSerxhs 我仍然在/无人问津的阴雨霉湿之地/和着雨音/唱着没有听众的歌曲

搬运于2025-08-24 22:32:37，当前版本为作者最后更新于2021-07-26 15:56:18，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

先考虑 $k=2$ 的情况．容易发现一条路径（或称为一组匹配）$(i,p_i)$ 对应一个排列 $\{p\}$，那么两条边 $(i,p_i),(j,p_j)~(i<j)$ 有交点等价于 $p_i>p_j$，这说明交点个数等于逆序对数．由于待求的是交点个数为偶数的减去交点个数为奇数的，容易联想到行列式．因此 $k=2$ 时答案即为邻接矩阵行列式的值．

对于 $k>2$ 但 $n_1=n_i=n_k$ 的情况，注意到一个结论：设 $f_i$ 表示第 $i$ 层和第 $i+1$ 层交点数为偶数的方案数，$g_i$ 表示第 $i$ 层和第 $i+1$ 层交点数为奇数的方案数，有 $(f_i-g_i)(f_{i+1}-g_{i+1})=(f_if_{i+1}+g_ig_{i+1})-(f_ig_{i+1}+g_if_{i+1})$，可以发现正好是第 $i$ 层到第 $i+2$ 层的答案（因为偶数依然是正的，奇数依然是负的）．这表明答案即为每层邻接矩阵对应行列式的乘积．

对于一般情况，考虑类似思路合并相邻两层．容易想到将邻接矩阵相乘即可计算第 $i$ 层到第 $i+2$ 层的邻接矩阵．可以画图证明，将两条边缩为一条边后，交点奇偶性不变．故答案即为邻接矩阵依次相乘后所得 $n_1\times n_k$ 矩阵的行列式．从 $n_1=n_k$ 以及上一做法结合结论 $|\mathrm {AB}|=|\mathrm A||\mathrm B|$ 可以看出这一结论十分自然．

int cal(int a[][N],register int n)
{
	register int i,j,k,r=1,fh=0,l;
	for (i=1;i<=n;i++)
	{
		for (j=i;j<=n;j++) if (a[j][i]) break;
		if (j>n) return 0;
		if (i!=j) {swap(a[j],a[i]);fh^=1;}
		r=(ll)r*a[i][i]%p;
		k=ksm(a[i][i],p-2);
		for (j=i;j<=n;j++) a[i][j]=(ll)a[i][j]*k%p;
		for (j=i+1;j<=n;j++)
		{
			a[j][i]=p-a[j][i];
			for (k=i+1;k<=n;k++) a[j][k]=(a[j][k]+(ll)a[j][i]*a[i][k])%p;
			a[j][i]=0;
		}
	}
	if (fh) return (p-r)%p;
	return r;
}
char s[N];
int a[N][N],c[N][N],d[N][N],b[N],f[N];
int T,n,m,i,j,k,x,y,z,ans,la,ksiz,ks;
void mul(int n,int m,int l)
{
	int i,j,k;
	for (i=1;i<=n;i++) for (j=1;j<=l;j++) d[i][j]=0;
	for (i=1;i<=n;i++) for (k=1;k<=m;k++) for (j=1;j<=l;j++) d[i][j]=(d[i][j]+(ll)a[i][k]*c[k][j])%p;
	for (i=1;i<=n;i++) for (j=1;j<=m;j++) a[i][j]=0;
	for (i=1;i<=m;i++) for (j=1;j<=l;j++) c[i][j]=0;
	for (i=1;i<=n;i++) for (j=1;j<=l;j++) a[i][j]=d[i][j];
}
int main()
{
	read(T);
	while (T--)
	{
		read(k);
		for (i=1;i<=k;i++) read(b[i]);
		for (i=1;i<k;i++) if (b[i]!=b[i+1]) break;
		memset(a,0,sizeof a);
		memset(c,0,sizeof c);
		read(f,k-1);m=f[1];
		while (m--) read(x,y),a[x][y]=1;n=b[1];
		for (i=2;i<k;i++)
		{
			m=f[i];
			while (m--) read(x,y),c[x][y]=1;
			mul(n,b[i],b[i+1]);
		}
		enter(cal(a,n));
	}
}