题解：P10216 【模板】Pfaffian

$\text{Pfaffian}$ 与图的匹配问题密切相关，是一个暂时比较冷门的线代科技工具。

我们定义一个长度为 $2n$ 的排列 $\pi$ 是一个完美匹配，当且仅当：

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

2. $\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^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$ 是反对称矩阵，所以这边也要取相反数，于是贡献就抵消了。

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

1. $\text{Pf}(BAB^T)=\det(B)\text{Pf}(A)$

2. $\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}$ 哦！