自动搬运

查看原文

来自洛谷，原作者为

	IdnadRev 你要把眼泪汇编成册

搬运于2025-08-24 22:55:49，当前版本为作者最后更新于2024-04-08 15:19:17，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

由于 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;
}