【模板记录】P10216 【模板】Pfaffian

· · 题解

由于 Pfaffian 值满足性质 \operatorname{Pf}(A)=\det(Q)\operatorname{Pf}(Q^TAQ)，对于初等行列变换矩阵 Q（除了乘常数），我们有 \operatorname{Pf}(A)=\operatorname{Pf}(Q^TAQ)。类似行列式求值，这为我们提供了一个使用合同变换对 A 消元以求出 Pfaffian 值的算法——

从 1 到 n-1 枚举每个奇数 i，若 A_{i,i+1} 处为零，我们可以找到某个非零位置 A_{p,i+1}，并同时交换第 p 列与第 i+1 列，第 p 行与第 i+1 行（因为变换形如 A\rightarrow Q^TAQ）。

接下来我们用第 i+1 列来消去所有 A_{i,p},p>i+1 的值，只需以 -\frac{A_{i,p}}{A_{i,i+1}} 的系数，将第 i+1 列加到第 p 列，将第 i+1 行加到第 p 行。

对于最终的反对称矩阵 A，每个奇数 i 都满足，A 第 i 行的第 i+2 列到第 n 列均为零（由反对称性，对第 i 列亦然），此时 \operatorname{Pf}(A)=\prod A_{2k-1,2k}。

具体实现中，我们可以只维护矩阵主对角线上方的元素，但是需谨慎处理对称产生的正负号。

#include<bits/stdc++.h>
using namespace std;
const int maxn=505,mod=1000000007;
int n,ans,flg;
int a[maxn][maxn];
int ksm(int a,int b) {
    int res=1;
    while(b) {
        if(b&1)
            res=1ll*res*a%mod;
        a=1ll*a*a%mod,b>>=1;
    }
    return res;
}
int main() {
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
        for(int j=i+1; j<=n; j++)
            scanf("%d",&a[i][j]);
    for(int i=1; i<=n; i+=2) {
        int p=i+1;
        for(int j=i+2; j<=n; j++)
            if(a[i][j]) {
                p=j;
                break;
            }
        if(p!=i+1) {
            flg^=1;
            for(int j=1; j<=i; j++)
                swap(a[j][i+1],a[j][p]);
            for(int j=i+2; j<p; j++)
                swap(a[i+1][j],a[j][p]),a[i+1][j]=mod-a[i+1][j],a[j][p]=mod-a[j][p];
            a[i+1][p]=mod-a[i+1][p];
            for(int j=p+1; j<=n; j++)
                swap(a[i+1][j],a[p][j]);
        }
        int iv=ksm(a[i][i+1],mod-2);
        for(int j=i+2; j<=n; j++)
            if(a[i][j]) {
                int coef=1ll*(mod-a[i][j])*iv%mod;
                for(int k=1; k<=i; k++)
                    a[k][j]=(a[k][j]+1ll*coef*a[k][i+1])%mod;
                for(int k=i+2; k<j; k++)
                    a[k][j]=(a[k][j]+1ll*(mod-coef)*a[i+1][k])%mod;
                for(int k=j+1; k<=n; k++)
                    a[j][k]=(a[j][k]+1ll*coef*a[i+1][k])%mod;
            }
    }
    ans=1;
    for(int i=1; i<=n; i+=2)
        ans=1ll*ans*a[i][i+1]%mod;
    printf("%d\n",flg==0? ans%mod:(mod-ans)%mod);
    return 0;
}