QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#787924 | #6623. Perfect Matchings | Kopicy | ML | 0ms | 3876kb | C++23 | 2.4kb | 2024-11-27 15:15:42 | 2024-11-27 15:15:43 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, a, b) for(int i=(a);i<=(b);++i)
#define per(i, a, b) for(int i=(a);i>=(b);--i)
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vv vector
#define sz(x) (int)x.size()
#define endl "\n"
const int N = 5005, mod = 998244353, inf = 2e9;
int f[N];
int qpow(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = 1LL * res * a % mod;
a = 1LL * a * a % mod;
b >>= 1;
}
return res;
}
int inv(int x) {
return qpow(x, mod - 2);
}
int C(int n, int m) {
if (n < m) return 0;
return 1LL * f[n] * inv(f[n - m]) % mod * inv(f[m]) % mod;
}
void add(int &x, int y) {
x = (1LL * x + y + mod) % mod;
}
void solve() {
int n;
cin >> n;
n *= 2;
vv<vv<int>> adj(n + 1);
rep(i, 1, n - 1) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
int sum = 0;
vv dp(n + 5, vv(n + 5, vv<int>(2)));
vv g(n + 5, vv<int>(2));
vv<int> siz(n + 1);
function<void(int, int)> dfs = [&](int u, int pr) {
siz[u] = 1;
dp[u][0][0] = 1;
for (int v: adj[u]) {
if (v == pr) continue;
dfs(v, u);
per(i, siz[u], 0)rep(j, 0, siz[v]) {
add(g[i + j][0],
1LL * dp[u][i][0] * (dp[v][j][0] + dp[v][j][1]) % mod);
add(g[i + j][1],
1LL * dp[u][i][1] * (dp[v][j][0] + dp[v][j][1]) % mod);
add(g[i + j + 1][1],
1LL * dp[u][i][0] * (dp[v][j][0]) % mod);
}
siz[u] += siz[v];
rep(i, 0, siz[u]) {
rep(j, 0, 1) {
dp[u][i][j] = g[i][j];
g[i][j] = 0;
}
}
}
};
dfs(1, 0);
rep(i, 0, n - 1) {
if (n / 2 - i < 0) break;
add(sum, 1LL * (1LL * dp[1][i][0] + dp[1][i][1]) % mod *
C(n - 2 * i, n / 2 - i) % mod * f[n / 2 - i] % mod *
inv(qpow(2, n / 2 - i) % mod) % mod * qpow(-1, i));
}
cout << sum << endl;
}
signed main() {
IOS
f[0] = 1;
rep(i, 1, N - 1) {
f[i] = 1LL * f[i - 1] * i % mod;
}
int64_t tt = 1;
//cin >> tt;
rep(kase, 1, tt) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3584kb
input:
2 1 2 1 3 3 4
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
3 1 2 2 3 3 4 4 5 5 6
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
10 2 1 3 2 4 2 5 3 6 3 7 5 8 4 9 3 10 5 11 3 12 9 13 11 14 8 15 5 16 1 17 4 18 1 19 11 20 19
output:
223263378
result:
ok 1 number(s): "223263378"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
10 2 1 3 1 4 1 5 1 6 5 7 3 8 7 9 3 10 2 11 3 12 5 13 12 14 10 15 11 16 10 17 4 18 14 19 4 20 4
output:
225215244
result:
ok 1 number(s): "225215244"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
10 2 1 3 1 4 3 5 3 6 5 7 3 8 5 9 3 10 8 11 2 12 1 13 11 14 2 15 3 16 3 17 2 18 11 19 10 20 3
output:
210104685
result:
ok 1 number(s): "210104685"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
10 2 1 3 2 4 3 5 1 6 2 7 5 8 2 9 3 10 2 11 10 12 7 13 12 14 2 15 2 16 15 17 2 18 6 19 15 20 8
output:
211263144
result:
ok 1 number(s): "211263144"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
10 2 1 3 2 4 3 5 2 6 2 7 1 8 7 9 3 10 8 11 5 12 6 13 11 14 8 15 1 16 13 17 2 18 14 19 11 20 12
output:
226024809
result:
ok 1 number(s): "226024809"
Test #8:
score: -100
Memory Limit Exceeded
input:
1977 2 1 3 1 4 1 5 4 6 4 7 1 8 3 9 5 10 2 11 3 12 2 13 3 14 2 15 9 16 9 17 2 18 17 19 5 20 16 21 2 22 2 23 15 24 16 25 22 26 14 27 6 28 4 29 24 30 25 31 28 32 15 33 27 34 32 35 24 36 10 37 18 38 15 39 33 40 3 41 27 42 3 43 35 44 15 45 11 46 19 47 21 48 4 49 28 50 6 51 3 52 14 53 14 54 14 55 25 56 18...
output:
337494603