QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#948296#10215. Gona Guniopen your brain (Zhi Zhang, Yanru Guan, Jianfeng Zhu)AC ✓1455ms539636kbC++142.5kb2025-03-22 23:39:062025-03-22 23:39:06

Judging History

This is the latest submission verdict.

  • [2025-03-22 23:39:06]
  • Judged
  • Verdict: AC
  • Time: 1455ms
  • Memory: 539636kb
Show
  • [2025-03-22 23:39:06]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
int n,m,f[300001][201][2],sz[300001],g[201][2][3],h[201][2][3];
vector<int>E[300010];
int S[210][210];
int F[210];
void update(int &x,int y) { x+=y; if (x>=mod) x-=mod; }
void dfs(int u,int pre){
    for(int v:E[u]) if(v^pre) dfs(v,u);
    sz[u]=0;
    for(int i=0;i<2;i++) for(int j=0;j<3;j++) g[0][i][j]=0;
    g[0][0][0]=1;
    for(int v:E[u]) if(v^pre){
        sz[u]+=sz[v];
        for(int i=0;i<=min(sz[u],m);i++) for(int j=0;j<2;j++) for(int k=0;k<3;k++) h[i][j][k]=0;
        for(int i=0;i<=min(sz[u]-sz[v],m);i++) for(int j=0;j<2;j++) for(int p=0;p<3;p++) if(g[i][j][p]) for(int k=0;k<=sz[v]&&i+k<=m;k++) for(int l=0;l<2;l++) if(f[v][k][l]){
            h[i+k][j|l][min(p+1,2)]=(h[i+k][j|l][min(p+1,2)]+1ll*g[i][j][p]*f[v][k][l])%mod;
        }
        for(int i=0;i<=min(sz[u]-sz[v],m);i++) for(int j=0;j<2;j++) for(int k=0;k<3;k++) update(h[i][j][k],g[i][j][k]);
        for(int i=0;i<=min(sz[u],m);i++) for(int j=0;j<2;j++) for(int k=0;k<3;k++) g[i][j][k]=h[i][j][k];
    }
    sz[u]++;
    for(int i=0;i<=m;i++) for(int j=0;j<2;j++) f[u][i][j]=0;
    for(int i=0;i<sz[u]&&i<=m;i++) for(int k=0;k<3;k++){
        if(k==2){
            update(g[i][1][k],g[i][1][k]);
            update(g[i][0][k],g[i][0][k]);
        }
        if(i<m) update(F[i+1],g[i][1][k]);
        update(F[i],g[i][1][k]);
        update(F[i],g[i][0][k]);

        if(k==1){
            update(g[i][1][k],g[i][1][k]);
            update(g[i][0][k],g[i][0][k]);
        }
        
        if(i<m) update(f[u][i+1][0],g[i][1][k]);
        update(f[u][i][0],g[i][1][k]);
        update(f[u][i][1],g[i][0][k]);
    }
}
void sol(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) E[i].clear();
    for(int i=1,u,v;i<n;i++) scanf("%d%d",&u,&v),E[u].push_back(v),E[v].push_back(u);
    for(int i=0;i<=m;i++) F[i]=0;
    dfs(1,0);
    // for(int u=1;u<=n;u++) for(int i=0;i<=m;i++) for(int j=0;j<2;j++) for(int k=0;k<2;k++) update(F[i],f[u][i][j][k]);
    for (int j=1,t=1;j<=m;j++) {
        t=(ll)t*j%mod;
        F[j]=(ll)F[j]*t%mod;
    }
    int res=0;
    for (int j=0;j<=m;j++) {
        update(res,(ll)S[m][j]*F[j]%mod);
    }
    printf("%d\n",res);
}
int main(){
    for (int n=0;n<=200;n++) {
        for (int k=0;k<=n;k++) {
            if (k==0) S[n][k]=(n==0);
            else S[n][k]=(S[n-1][k-1]+(ll)k*S[n-1][k])%mod;
        }
    }
    int T;
    scanf("%d",&T);
    while(T--) sol();
}
源文件, 语言: C++14

这程序好像有点Bug，我给组数据试试？

詳細信息

Test #1:

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

input:

2
3 1
1 2
1 3
20 200
1 2
1 3
2 4
1 5
5 6
1 7
6 8
6 9
3 10
4 11
6 12
11 13
4 14
13 15
15 16
6 17
13 18
15 19
13 20

output:

4
286430678

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 504ms
memory: 497672kb

input:

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

output:

247999825

result:

ok single line: '247999825'

Test #3:

score: 0
Accepted
time: 134ms
memory: 14244kb

input:

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

output:

206703729
241517344
965256040
953191893
971103184
611763581
951769747
605254273
515657073
26158774
230121672
742384467
504292176
95015638
209242429
591984607
47728881
658540538
686302223
589359656
153765564
462000121
877695624
168867090
447225696
468677488
440776261
374615358
105981576
120340771
617...

result:

ok 3000 lines

Test #4:

score: 0
Accepted
time: 650ms
memory: 492980kb

input:

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

output:

634171363

result:

ok single line: '634171363'

Test #5:

score: 0
Accepted
time: 1455ms
memory: 539636kb

input:

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

output:

378891816

result:

ok single line: '378891816'

Test #6:

score: 0
Accepted
time: 296ms
memory: 492592kb

input:

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

output:

435358080

result:

ok single line: '435358080'

Test #7:

score: 0
Accepted
time: 1055ms
memory: 493040kb

input:

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

output:

220992079

result:

ok single line: '220992079'

Test #8:

score: 0
Accepted
time: 1381ms
memory: 534780kb

input:

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

output:

872442796

result:

ok single line: '872442796'

Test #9:

score: 0
Accepted
time: 895ms
memory: 515920kb

input:

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

output:

77589834

result:

ok single line: '77589834'

Test #10:

score: 0
Accepted
time: 598ms
memory: 502388kb

input:

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

output:

137591617

result:

ok single line: '137591617'

Test #11:

score: 0
Accepted
time: 500ms
memory: 493036kb

input:

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

output:

529039223

result:

ok single line: '529039223'

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

伺服器時間: 2025-04-02 17:40:51 | 開源專案