题解：P11817 [PA 2019 Final] 数图 / Grafy

· · 题解

直接对邻接表计数，即计数满足 a_{2i},a_{2i+1},i 两两不同且每个数都出现恰好两次的序列 a_{0\dots 2n-1}。由于这里认为出边有序，求出答案后要除以 2^n。进一步地，我们也可以使入边也有序（再除以一个 2^n），也就是让 2i 和 2i+1 来指代 i 的两条入边。即计数满足如下条件的排列 a_{0\dots 2n-1}：\forall i,\lfloor a_{2i}/2\rfloor\ne \lfloor a_{2i+1}/2\rfloor\land \lfloor a_{2i}/2\rfloor\ne i\land \lfloor a_{2i+1}/2\rfloor\ne i。

算子法告诉我们贡献可以改写成如下形式（记 b_i=\lfloor a_i/2\rfloor）：

\begin{aligned} &\prod_{i=0}^{n-1}[b_{2i}\ne i][b_{2i+1}\ne i][b_{2i}\ne b_{2i+1}]\\ =&\prod_{i=0}^{n-1}1-[b_{2i}=i]-[b_{2i+1}=i]-[b_{2i}=b_{2i+1}]+[b_{2i}=i][b_{2i+1}=i]+[b_{2i}=i][b_{2i}=b_{2i+1}]+[b_{2i+1}=i][b_{2i}=b_{2i+1}]-[b_{2i}=i][b_{2i+1}=i][b_{2i}=b_{2i+1}]\\ =&\prod_{i=0}^{n-1}1-[b_{2i}=i]-[b_{2i+1}=i]-[b_{2i}=b_{2i+1}]+2[b_{2i}=b_{2i+1}=i]\\ \end{aligned}

枚举贡献形式，设分别有 i,j,k,t 个位置 u 以 -[b_{2u}=u]、-[b_{2u+1}=u]、-[b_{2u}=b_{2u+1}]、2[b_{2u}=b_{2u+1}=u] 的形式产生贡献（这一步相当于是在钦定），剩余 w=n-i-j-k-t 个 u 的贡献就是 1。

考虑计数此时能产生贡献的排列 a，推一推可以得到式子：

\sum_{i+j+k+t+w=n}{n\choose i,j,k,t,w}(n+w-k-t)!\color{red}{(-2)^i}\color{blue}{(-2)^j}\color{green}{(-1)^k{w+k\choose k}k!2^k}\color{purple}{2^{2t}}

（这里标为红、蓝、绿、紫的部分分别是 i,j,k,t 的贡献。）

将 i+j 代换为 p，合并一些项：

\sum_{p+k+t+w=n}{n\choose p,k,t,w}(n+w-k-t)!(-1)^{p+k}2^{k+2p+2t}{w+k\choose k}k!

这就给出了一个 \Theta(n^3) 的做法，可以通过 easy version。

#include <iostream>

using namespace std;

const int kN = 501;

int n, kM, fc[kN * 2], ic[kN], p2[kN * 2];

int inv(int a, int m = kM) { return a == 1 ? 1 : m - 1ll * inv(m % a, a) * m / a; }

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> kM;
  for (int i = fc[0] = 1; i <= n * 2; ++i) {
    fc[i] = 1ll * fc[i - 1] * i % kM;
  }
  ic[n] = inv(fc[n]);
  for (int i = n; i >= 1; --i) {
    ic[i - 1] = 1ll * ic[i] * i % kM;
  }
  for (int i = p2[0] = 1; i <= n * 2; ++i) {
    p2[i] = p2[i - 1] * 2 % kM;
  }
  int ans = 0;
  for (int i = 0; i <= n; ++i) {
    for (int j = 0; i + j <= n; ++j) {
      for (int k = 0; i + j + k <= n; ++k) {
        int t = n - i - j - k;
        ans = (ans + 1ll * ((i + j & 1) ? kM - 1 : 1) * fc[n] % kM * ic[i] % kM * ic[j] % kM * ic[k] % kM * ic[t] % kM * fc[n + t - j - k] % kM * p2[2 * (i + k) + j] % kM * fc[j + t] % kM * ic[t]) % kM;
      }
    }
  }
  cout << 1ll * ans * inv(p2[n * 2]) % kM;
  return 0;
}