题目描述
http://codeforces.com/gym/102956/problem/G
Solution
注意到树如果存在完美匹配，那么这个完美匹配是唯一的
那么答案就是将 $n$ 个点分成 $\frac n2$ 的方案乘上将 $\frac n2$ 连成一棵树的方案
注意到这 $\frac n2$ 我们应该认为是带标号的，所以方案数应该为 $(\frac n2)^{\frac n2 - 2}$
另外注意到对于每条边有 $4$ 种连法
所以最后的答案为 $\frac{n!}{(2!)^{\frac n2}\cdot (\frac n2)!}\cdot (\frac n2)^{\frac n2 - 2}\cdot 4^{\frac n2-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
| #include <iostream>
#include <cmath>
#include <vector>
#define maxn 1000010
#define ll long long
using namespace std;
const int p = 998244353;
ll pow_mod(ll x, ll n) {
ll s = 1;
for (; n; n >>= 1, x = x * x % p)
if (n & 1) s = s * x % p;
return s;
}
int n;
ll fac[maxn], inv[maxn];
void init_C(int n) {
fac[0] = 1; for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % p;
inv[n] = pow_mod(fac[n], p - 2);
for (int i = n - 1; ~i; --i) inv[i] = inv[i + 1] * (i + 1) % p;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n; init_C(n);
if (n & 1) return cout << "0\n", 0;
if (n == 2) return cout << "1\n", 0;
cout << fac[n] * pow_mod(pow_mod(2, n / 2), p - 2) % p * inv[n / 2] % p * pow_mod(n / 2, n / 2 - 2) % p * pow_mod(4, n / 2 - 1) % p << "\n";
return 0;
}
|