QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#787924#6623. Perfect MatchingsKopicyML 0ms3876kbC++232.4kb2024-11-27 15:15:422024-11-27 15:15:43

Judging History

你现在查看的是最新测评结果

  • [2024-11-27 15:15:43]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:3876kb
  • [2024-11-27 15:15:42]
  • 提交

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

result: