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

SSerxhs · 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));
    }
}