带标号联通欧拉图计数

失联人员回归系列

欧拉图计数

题目大意

给定 \(n\) 个点, 求合法有标号联通欧拉图的个数 \((mod ~~998244353)\)

解题思路

我们考虑到直接求并不是很好求啊, 所谓正难则反嘛(事实就是我反着也不会)我们考虑用 \(n\) 个点的不一定联通的欧拉图的个数减去一定不连通的欧拉图的个数就好了

所以我们设 \(f_i\)\(i\) 个点联通的欧拉图的个数, \(g_i\)\(i\) 个点不一定联通的欧拉图的个数

很显然 \(g_i\)\(2 ^ {\binom{i - 1}{2}}\), 这里解释一下为什么

如果我们只考虑 \(i - 1\) 个点, 将它们之间任意连边, 图的数量就是 \(2 ^ {\binom{i - 1}{2}}\), 我们考虑如果这 \(i - 1\) 个点里如果有奇数度数的点, 我们就把最后第 \(i\) 个点向它连边, 这样就可一保证 \(i - 1\) 个点里没有奇数度数的点了, 那为什么最后一个点的度数一定是偶数呢, 因为一个图的点的度数的总和一定是个偶数(每条边贡献两个度数), 所以 \(i - 1\) 个点里奇数度数的点一定是偶数个, 所以最后一个点的度数也是偶数

然后显然有转移 \[ f_i = g_i - \sum _ {j = 1} ^ {i -1}f_j * g_{i - j} * \binom{i - 1}{j - 1} \] 这里解释一下为什么最后乘上的是 \(\binom{i - 1}{j - 1}\) 而不是 \(\binom{i}{j}\), 经过实践我们发现乘 \(\binom{i}{j}\) 是会算重的, 我们考虑钦定一个点一定在联通欧拉图中( \(f\) 所代表的图), 然后在 \(i - 1\) 个点中再选 \(j - 1\) 个点(因为带标号).

代码 :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = 2e3 + 5;
const int P = 1e9 + 7;

int n, f[maxn], C[maxn][maxn], g[maxn];

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

inline int pls(int x, int y) {x += y; return x >= P ? x - P : (x < 0 ? x + P : x);}
inline int mul(int x, int y) {LL rnt = 1ll * x * y; return rnt >= P ? rnt % P : rnt;}
inline int mul(int a, int b, int c) {return mul(a, mul(b, c));}

inline int ksm(int x, int k) {
int cnt = 1;
while(k) {
if(k & 1) cnt = mul(cnt, x);
x = mul(x, x); k >>= 1;
} return cnt;
}

inline void Prep(int n) {
C[0][0] = 1;
for(register int i = 1; i <= n; i++) {
C[i][0] = 1;
for(register int j = 1; j <= i; j++)
C[i][j] = pls(C[i - 1][j - 1], C[i - 1][j]);
}

g[1] = 1; g[2] = 1;
for(register int i = 3; i <= n; i++)
g[i] = ksm(2, C[i - 1][2]);
}

int main() {
n = read(); Prep(n);
for(register int i = 1; i <= n; i++) {
f[i] = g[i];
for(register int j = 1; j < i; j++) f[i] = pls(f[i], -mul(f[j], g[i - j], C[i - 1][j - 1]));
}

cout << f[n];
return 0;
}
/*
*/