由i个点和j个点组成的二分图个数为 $3_{ij}$,减去不联通的部分得到得到由i,j个点组成的联通二分图个数
$g_{i,j} = 3_{ij} - \sum_{k=1}^i \sum_{l=0}^j g_{k,l} C_{i-1,k-1} C_{j,l} 3_{(i-k)(j-l)}$
然后再dp一遍
#include <bits/stdc++.h> using namespace std; #define rep(i, j, k) for (int i = int(j); i <= int(k); ++ i) #define dwn(i, j, k) for (int i = int(j); i >= int(k); -- i) typedef long long LL; const LL MOD = 175781251; const int N = 107; LL fac[N], inv[N], pw[N * N], g[N][N], f[N]; inline LL comb(LL n, LL m) { return fac[n] * inv[m] % MOD * inv[n - m] % MOD; } int main() { fac[0] = 1; rep(i, 1, N - 1) fac[i] = fac[i - 1] * i % MOD; inv[0] = inv[1] = 1; rep(i, 2, N - 1) inv[i] = MOD - (MOD / i) * inv[MOD % i] % MOD; rep(i, 2, N - 1) (inv[i] *= inv[i - 1]) %= MOD; pw[0] = 1; rep(i, 1, N * N - 1) pw[i] = pw[i - 1] * 3 % MOD; rep(i, 1, 100) rep(j, 0, 100 - i) { g[i][j] = pw[i * j]; // A集合中i 个点标号 1 -i, B集合中j个点标号1-j // 枚举A集合中第一个点所在联通二分图 rep(k, 1, i) rep(l, 0, j) { if (k == i && l == j) continue; g[i][j] += MOD - g[k][l] * comb(i - 1, k - 1) % MOD * comb(j, l) % MOD * pw[(i - k) * (j - l)] % MOD; g[i][j] %= MOD; } } f[0] = 1; rep(i, 1, 100) rep(j, 0, i - 1) rep(k, 0, i - 1 - j) { f[i] += g[j + 1][k] * comb(i - 1, j) % MOD * comb(i - 1 - j, k) % MOD * f[i - 1 - j - k] % MOD; f[i] %= MOD; } int n; while (scanf("%d", &n), n) { cout << f[n] << '\n'; } }