QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#763817#6623. Perfect MatchingsSymmetreeTL 940ms74028kbC++171.3kb2024-11-19 22:14:422024-11-19 22:14:42

Judging History

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

  • [2024-11-19 22:14:42]
  • 评测
  • 测评结果：TL
  • 用时：940ms
  • 内存：74028kb
查看
  • [2024-11-19 22:14:42]
  • 提交

answer

#include<bits/stdc++.h>
const int N = 4e3+5, mod = 998244353;
int n, x, y, siz[N], f[2][N][N], h[N];
std::vector<int> g[N];
inline void upd(int &a, int b) {
    a += b, a %= mod;
}
void dfs(int x, int fa) {
    f[0][x][0] = 1, siz[x] = 1;
    for(int y: g[x]) {
        if(y == fa) continue;
        dfs(y, x);
        for(int i = std::min(n, siz[x] + siz[y] - 1); i >= 1; --i)
            for(int j = i - siz[x]; j <= i && j < siz[y]; ++j) {
                if(j) upd(f[0][x][i], 1ll * f[0][x][i - j] * (f[0][y][j] + f[1][y][j]) % mod);
                if(j) upd(f[1][x][i], 1ll * f[1][x][i - j] * (f[0][y][j] + f[1][y][j]) % mod);
                if(j < i) upd(f[1][x][i], 1ll * f[0][x][i - j - 1] * f[0][y][j] % mod);
            }
        siz[x] += siz[y];
    }
}
signed main() {
    scanf("%d", &n);
    h[0] = 1;
    for(int i = 1; i <= n; ++i) h[i] = 1ll * h[i - 1] * (2 * i - 1) % mod;
    for(int i = 1; i < 2 * n; ++i)
        scanf("%d%d", &x, &y), g[x].push_back(y), g[y].push_back(x);
    dfs(1, 0);
    int ans = 0;
    for(int i = 0; i <= n; ++i) {
        if(i & 1) upd(ans, mod - 1ll * (f[0][1][i] + f[1][1][i]) * h[n - i] % mod);
        else upd(ans, 1ll * (f[0][1][i] + f[1][1][i]) * h[n - i] % mod);
    }
    printf("%d\n", ans);
    return 0;
}
源文件, 语言: C++17

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 4020kb

input:

2
1 2
1 3
3 4

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 0ms
memory: 4036kb

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: 1ms
memory: 4124kb

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: 4112kb

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: 4164kb

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: 3984kb

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: 1ms
memory: 6080kb

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: 0
Accepted
time: 395ms
memory: 73664kb

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:

ok 1 number(s): "337494603"

Test #9:

score: 0
Accepted
time: 722ms
memory: 71736kb

input:

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

output:

850212664

result:

ok 1 number(s): "850212664"

Test #10:

score: 0
Accepted
time: 378ms
memory: 73676kb

input:

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

output:

148051811

result:

ok 1 number(s): "148051811"

Test #11:

score: 0
Accepted
time: 758ms
memory: 71724kb

input:

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

output:

280704181

result:

ok 1 number(s): "280704181"

Test #12:

score: 0
Accepted
time: 669ms
memory: 73664kb

input:

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

output:

627986542

result:

ok 1 number(s): "627986542"

Test #13:

score: 0
Accepted
time: 663ms
memory: 74028kb

input:

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

output:

927794050

result:

ok 1 number(s): "927794050"

Test #14:

score: 0
Accepted
time: 478ms
memory: 73904kb

input:

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

output:

685071441

result:

ok 1 number(s): "685071441"

Test #15:

score: 0
Accepted
time: 552ms
memory: 73520kb

input:

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

output:

632229124

result:

ok 1 number(s): "632229124"

Test #16:

score: 0
Accepted
time: 553ms
memory: 73784kb

input:

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

output:

175426091

result:

ok 1 number(s): "175426091"

Test #17:

score: 0
Accepted
time: 940ms
memory: 71988kb

input:

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

output:

620932394

result:

ok 1 number(s): "620932394"

Test #18:

score: 0
Accepted
time: 558ms
memory: 71792kb

input:

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

output:

990615942

result:

ok 1 number(s): "990615942"

Test #19:

score: 0
Accepted
time: 761ms
memory: 74004kb

input:

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

output:

814855336

result:

ok 1 number(s): "814855336"

Test #20:

score: -100
Time Limit Exceeded

input:

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

output:

935127715

result:
English 繁體中文 简体中文

伺服器時間: 2024-12-12 00:08:35 | 開源專案