题解：P10216 【模板】Pfaffian

lalaouye · 2025-07-25 12:47:18 · 题解

我们定义一个长度为 $2n$ 的排列 $\pi$ 是一个完美匹配，当且仅当： 1. $\forall 1\le i\le n,\pi_{2i-1}<\pi_{2i}

\forall 1\le i<n,\pi_{2i-1}<\pi_{2i+1}

其实就是用排列中的 n 对 (\pi_{2i-1},\pi_{2i}) 刻画了一组完美匹配。记 \mathcal{M}_{2n} 为长度为 2n 的完美匹配构成集合。

对于 2n\times 2n 的反对称矩阵 A，定义 A 的 \text{Pfaffian} 为

\text{Pf}(A)=\sum_{\pi\in\mathcal{M}_{2n}} \text{sgn}(\pi)\prod_{i=1}^nA_{\pi_{2i-1},\pi_{2i}}

其中 \text{sgn}(\pi) 就是 (-1)^{\text{inv}(\pi)}，\text{inv}(\pi) 则表示逆序对个数。

我们不难证明对于完美匹配排列，其逆序对个数的奇偶性，就是把 (\pi_{2i-1},\pi_{2i}) 视为一个区间，相交但不包含的区间对数的奇偶性，证明可以考虑一个区间两个数的贡献，这就不细说了。

关于该函数是存在一些性质的，下面我们一个一个讨论。

在讨论性质之前，我们来证一个比较厉害的东西：

\text{Pf}(A)=\frac{1}{2^{n}n!}\sum_{\pi}\text{sgn}(\pi)\prod_{i=1}^n A_{\pi_{2i-1},\pi_{2i}}

证明我们可以考虑，我们对于一个排列还是令 (\pi_{2i-1},\pi_{2i}) 表示一组匹配，那么对于本质相同的匹配，我们考虑如果我们要交换一组匹配在排列中的位置，那么 \text{sgn} 不变，因为我们不难发现不管相对位置如何，相交但不包含稳定产生一次奇偶性改变，否则不变。

而如果我们要交换一组匹配的前后位置，那么 \text{sgn} 就要取相反数，但是 A 是反对称矩阵，所以这边也要取相反数，于是贡献就抵消了。

关于该函数主要有以下两个性质：

\text{Pf}(BAB^T)=\det(B)\text{Pf}(A)
\det(A)=\text{Pf}^2(A)

第二个性质貌似题解区的证法是有问题的，而且网上的证明跟看英文一样，对于本蒟蒻来说太复杂了，我这边可以提供一个比较简单的证明。

我们先来证第一个，其中 i_1,j_1,\cdots,i_n,j_n 构成一个长为 2n 的排列，(i_t,j_t) 表示一组匹配：

\begin{aligned}\text{Pf}(BAB^T)&=\frac 1 {2^nn!}\sum_{i,j}\text{sgn}(i,j)\prod_{t=1}^n\sum_{k=1}^{2n}B_{i_t,k}\sum_{l=1}^{2n}A_{k,l}B_{j_t,l}\\&=\frac 1 {2^nn!}\sum_{i,j,k,l}\text{sgn}(i,j)\prod_{t=1}^n B_{i_t,k_t}A_{k_t,l_t}B_{j_t,l_t} \end{aligned}

然后我们接下来证明只需要计算 k\cup l 是排列的情况。如果存在 t_1,t_2 使得 k_{t_1}=k_{t_2}，我们交换 i_{t_1},i_{t_2} 发现贡献变成相反数，答案抵消。对于 l 类似。而如果存在 t_1,t_2 使得 k_{t_1}=l_{t_2}，那么我们交换 i_{t_1} 和 j_{t_2} 答案也能够抵消。

所以我们可以钦定 k\cup l 构成排列。之后我们定义 i\cup j=p,k\cup l=q，于是

\begin{aligned} \text{Pf}(BAB^T)&=\frac 1 {2^nn!}\sum_{p,q}\text{sgn}(p)\prod_{i=1}^{2n} B_{p_i,q_i} \prod_{i=1}^n A_{q_{2i-1},q_{2i}}\\&=\frac 1 {2^nn!}\sum_q \text{sgn}(q)(\sum_p\text{sgn}(p)\prod_{i=1}^{2n} B_{i,p_i})\prod_{i=1}^n A_{q_{2i-1},q_{2i}}\\&=\det(B)\text{Pf}(A) \end{aligned}

至于说为啥第二行乘了个 \text{sgn}(q)？因为 p 的含义已经改变了，它变成了两个排列的复合，所以需要多乘个 \text{sgn}(q)。

在证明第二个性质之前，我们可以先讲讲怎么快速计算 \text{Pf} 函数，我们可以利用第一条性质，对 A 进行初等变换，我们知道初等变换中除了乘一行的初等变换矩阵，其它的行列式绝对值都为 1，交换两行需要取 -1。

我们考虑把矩阵变成最容易计算答案的矩阵。我们从第一行开始，只关心奇数行，若当前考虑到第 i 行，我们找到 p 使得 A_{i,p} 不为 0，交换第 i+1 列与第 p 列，同时注意也要交换第 i+1 行和第 p 行。然后我们要把第 i 行，i+1 列后面的数全部消成 0，也就是对于 i+1<j\le 2n，我们要将第 j 列减去第 i+1 列乘以 \frac{A_{i,j}}{A_{i,i+1}}，同时将第 j 行减去第 i+1 行乘以 \frac {A_{i,j}}{A_{i,i+1}}。我们发现后面的操作不影响前面，不难发现这样变换后最后的答案一定是 \prod_{i=1}^n A_{2i-1,2i}。

会了这个就可以快乐的通过模板题了。但是别忘了我们还有一个历史遗留问题，也就是如何证明第二条性质。

我们考虑令 A=PDP^T，其中 D 就是我们刚刚过程变换完最后的矩阵。对于这个矩阵，我们是容易证明 \text{Pf}^2(D)=\det(D) 的。我们可以考虑归纳法，第一行只有 D_{1,2} 有值，那么 p_1=2，然后第二列只有 D_{2,1} 有值，那么 p_2=1，那么相当于我们的行列式需要乘以 D_{1,2}^2，以此类推我们发现

\det(D)=\prod_{i=1}^n D_{2i-1,2i}^2=\text{Pf}^2(D)

然后 \text{Pf}^2(A)=\det(P)^2\det(D)，又因为 \det(A)=\det(P)\det(D)\det(P^T)=\det(P)^2\det(D)，于是可以得知他们是相等的。

洛谷模板题的代码：

int n, a[N][N];
int32_t main () {
  n = rd ();
  rep (i, 1, n) {
    rep (j, i + 1, n) {
      a[i][j] = rd (); a[j][i] = -a[i][j];
    }
  }
  int ans (1);
  for (int i (1); i <= n; i += 2) {
    int j (i + 1);
    for (; j <= n && ! a[i][j]; ++ j) ++ j;
    if (j == n + 1) return puts ("0") * 0;
    if (j != i + 1) ans = -ans;
    swap (a[j], a[i + 1]);
    rep (k, 1, n) swap (a[k][j], a[k][i + 1]);
    rep (k, i + 2, n) {
      if (a[i][k]) {
        int v = a[i][k] * qpow (a[i][i + 1], P - 2) % P;
        rep (l, 1, n) {
          (a[l][k] -= v * a[l][i + 1]) %= P;
          (a[k][l] -= v * a[i + 1][l]) %= P;
        }
      }
    }
    ans = ans * a[i][i + 1] % P;
  }
  cout << (ans + P) % P;
}

第二个性质有什么用呢？我们发现这个式子非常纯，左边只有 \det，右边只有 \text{Pf}，而行列式的性质可多得去了！这样在偶数阶反对称矩阵中，\text{Pf} 函数拥有很多优良的性质。如果没有模数的话，我们可以直接算 \det 求 \text{Pf} 哦！