QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#962519#6223. 神经网络ETO_leader100 ✓199ms488576kbC++262.9kb2025-04-02 21:09:252025-04-02 21:09:26

Judging History

This is the latest submission verdict.

  • [2025-04-02 21:09:26]
  • Judged
  • Verdict: 100
  • Time: 199ms
  • Memory: 488576kb
  • [2025-04-02 21:09:25]
  • Submitted

answer

#include<bits/stdc++.h>
#define cir(i,a,b) for(int i=a;i<b;++i)
using namespace std;
using lint=long long;
static constexpr auto MOD=998244353;
class mathbase{
private:
    vector<lint> fct;
public:
    constexpr auto qpow(lint a,auto b) const{
        auto res=1ll;
        while(b){
            if(b&1) (res*=a)%=MOD;
            (a*=a)%=MOD;b>>=1;
        }
        return res;
    }
    constexpr auto inv(auto x) const{return qpow(x,MOD-2);}
    auto init(const auto n){
        fct.resize(n,1);
        cir(i,1,n) fct[i]=fct[i-1]*i%MOD;
    }
    auto fact(const auto x) const{return fct[x];}
    // static constexpr const auto lowbit(signed int x) noexcept(true)->
} math;
class tree{
private:
    vector<vector<int>> gr;
    vector<vector<lint>> uf,ug,uh;
    auto dfs(int u,int f=-1)->int{
        const auto n=(int)(gr.size());
        auto siz=0;
        uh[u][0]=1;
        for(auto&i:gr[u]) if(i!=f){
            const auto szv=dfs(i,u);
            vector<lint> cf(n+1),cg(n+1),ch(n+1);
            cir(w,0,siz+1) cir(vw,0,szv+1){
                (cf[w+vw]+=uf[u][w]*ug[i][vw]+uh[u][w]*uf[i][vw])%=MOD;
                (cg[w+vw]+=ug[u][w]*ug[i][vw])%=MOD;
                (ch[w+vw]+=uh[u][w]*ug[i][vw])%=MOD;
                (cg[w+vw+1]+=uf[u][w]*uf[i][vw]*2)%=MOD;
            }
            uf[u]=cf;ug[u]=cg;uh[u]=ch;
            siz+=szv;
        }
        ++siz;
        cir(i,0,siz) (ug[u][i+1]+=uf[u][i]*2+uh[u][i])%=MOD;
        cir(i,0,siz+1) (uf[u][i]+=uh[u][i])%=MOD;
        return siz;
    }
public:
    auto link(int u,int v){
        gr[u].emplace_back(v);
        gr[v].emplace_back(u);
    }
    auto init(){
        dfs(0);
        return ug[0];
    }
    tree(int _n):
        gr(_n),
        uf(_n,vector<lint>(_n+1)),
        ug(_n,vector<lint>(_n+1)),
        uh(_n,vector<lint>(_n+1)){}
};
auto init_q(const int n){
    vector q(n,vector<lint>(n));
    q[0][0]=1;
    cir(i,1,n) cir(j,1,n){
        (q[i][j]=q[i-1][j]*(i+j-1)+q[i-1][j-1])%=MOD;
    }
    cir(i,0,5){
        cir(j,0,5){
            clog<<q[i][j]<<' ';
        }
        clog<<'\n';
    }
    return q;
}
static constexpr auto maxn=(int)(5e3+7);
int main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);
    int n;cin>>n;vector<lint> f{1};
    math.init(maxn);
    auto siz=0;
    const auto q=init_q(maxn);
    cir(c,0,n){
        int m;cin>>m;tree gr(m);
        cir(i,0,m-1){
            int u,v;cin>>u>>v;--u;--v;
            gr.link(u,v);
        }
        auto g=gr.init();
        cir(i,0,m+1) cir(j,0,i) (g[j]+=((i-j)&1?(MOD-1):1)*q[i][j]%MOD*g[i])%=MOD;
        const auto lf=f;
        f=vector<lint>((siz+=m)+1);
        cir(i,0,(int)(lf.size())) cir(j,0,m+1) (f[i+j]+=lf[i]*g[j])%=MOD; 
    }
    auto ans=0ll;
    cir(i,1,(int)(f.size())) (ans+=f[i]*math.fact(i-1))%=MOD;
    cout<<ans<<'\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 5
Accepted
time: 41ms
memory: 199424kb

input:

3
4
2 1
4 3
3 1
5
4 5
3 4
3 2
1 2
1

output:

32824

result:

ok 1 number(s): "32824"

Test #2:

score: 5
Accepted
time: 46ms
memory: 199424kb

input:

4
3
1 2
3 1
3
2 1
3 1
5
3 4
5 4
2 3
2 1
4
2 1
3 2
4 3

output:

212823345

result:

ok 1 number(s): "212823345"

Test #3:

score: 5
Accepted
time: 46ms
memory: 199680kb

input:

300
1
1
2
1 2
2
2 1
2
2 1
2
1 2
1
2
2 1
1
2
1 2
1
2
2 1
2
1 2
2
1 2
2
1 2
2
2 1
1
1
1
1
1
2
2 1
1
1
1
2
2 1
2
2 1
1
2
2 1
2
1 2
1
2
1 2
1
1
2
2 1
1
1
2
1 2
2
1 2
2
2 1
1
2
1 2
1
2
2 1
1
2
2 1
2
1 2
1
1
2
1 2
2
1 2
2
2 1
2
1 2
2
1 2
2
2 1
2
1 2
2
1 2
2
1 2
1
1
2
2 1
2
2 1
1
2
2 1
1
1
2
1 2
1
1
2
1 2
...

output:

354818429

result:

ok 1 number(s): "354818429"

Test #4:

score: 5
Accepted
time: 36ms
memory: 199808kb

input:

300
2
2 1
2
1 2
3
1 2
2 3
2
2 1
1
2
1 2
2
2 1
1
2
1 2
3
1 2
3 1
3
3 1
2 1
1
2
2 1
3
1 3
1 2
3
3 1
1 2
1
1
2
1 2
2
2 1
2
2 1
2
1 2
2
2 1
2
2 1
1
2
1 2
2
1 2
3
1 2
1 3
3
3 1
2 1
3
1 2
3 1
3
1 3
1 2
1
3
2 1
1 3
2
2 1
3
3 2
1 2
1
3
2 3
2 1
3
1 2
1 3
1
1
3
1 2
1 3
1
3
1 3
1 2
3
2 1
1 3
3
3 1
1 2
3
1 2
2 ...

output:

163346936

result:

ok 1 number(s): "163346936"

Test #5:

score: 5
Accepted
time: 48ms
memory: 199936kb

input:

300
3
1 2
3 1
2
1 2
2
1 2
2
2 1
3
3 1
1 2
1
2
1 2
1
1
2
2 1
2
2 1
3
2 3
1 2
2
2 1
2
2 1
1
2
1 2
3
1 3
2 1
1
3
3 1
2 1
2
2 1
3
3 2
1 2
1
1
2
2 1
1
1
3
2 1
1 3
3
3 2
1 2
3
2 1
1 3
3
1 2
3 1
2
2 1
3
1 2
3 2
3
1 2
1 3
2
2 1
3
1 3
2 1
3
2 1
3 2
2
2 1
1
2
1 2
2
2 1
3
3 1
2 1
1
3
1 2
3 1
3
3 2
1 2
2
2 1
2
...

output:

623176801

result:

ok 1 number(s): "623176801"

Test #6:

score: 5
Accepted
time: 42ms
memory: 199808kb

input:

300
3
1 2
3 2
3
2 1
3 1
2
1 2
2
1 2
2
2 1
1
1
3
1 2
3 2
1
2
1 2
3
1 2
3 1
2
1 2
1
2
2 1
3
3 2
1 2
3
3 1
2 1
2
1 2
1
3
3 2
1 2
3
2 1
3 2
3
3 2
2 1
1
1
3
1 2
1 3
3
3 1
1 2
3
2 1
3 1
2
2 1
2
2 1
1
1
3
1 2
1 3
1
1
3
2 1
1 3
2
1 2
1
2
2 1
1
2
1 2
2
2 1
3
2 1
3 1
1
2
2 1
2
2 1
2
2 1
2
2 1
2
1 2
2
1 2
2
1 ...

output:

220324606

result:

ok 1 number(s): "220324606"

Test #7:

score: 5
Accepted
time: 49ms
memory: 199936kb

input:

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

output:

634594980

result:

ok 1 number(s): "634594980"

Test #8:

score: 5
Accepted
time: 49ms
memory: 199808kb

input:

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

output:

33435632

result:

ok 1 number(s): "33435632"

Test #9:

score: 5
Accepted
time: 49ms
memory: 199808kb

input:

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

output:

642271217

result:

ok 1 number(s): "642271217"

Test #10:

score: 5
Accepted
time: 50ms
memory: 199936kb

input:

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

output:

910594026

result:

ok 1 number(s): "910594026"

Test #11:

score: 5
Accepted
time: 120ms
memory: 252928kb

input:

59
1500
1206 1205
1192 1191
702 703
1412 1411
1060 1061
470 469
707 708
1133 1132
166 165
1197 1196
1215 1214
1030 1031
362 363
4 3
1167 1168
793 794
1418 1417
1195 1196
644 645
721 722
590 591
828 827
421 422
580 579
1186 1187
194 193
553 552
1430 1431
972 973
1398 1397
354 353
913 914
544 545
586 ...

output:

756407276

result:

ok 1 number(s): "756407276"

Test #12:

score: 5
Accepted
time: 120ms
memory: 252928kb

input:

59
1500
1206 1205
1192 1191
702 703
1412 1411
1060 1061
470 469
707 708
1133 1132
166 165
1197 1196
1215 1214
1030 1031
362 363
4 3
1167 1168
793 794
1418 1417
1195 1196
644 645
721 722
590 591
828 827
421 422
580 579
1186 1187
194 193
553 552
1430 1431
972 973
1398 1397
354 353
913 914
544 545
586 ...

output:

799821558

result:

ok 1 number(s): "799821558"

Test #13:

score: 5
Accepted
time: 124ms
memory: 252672kb

input:

59
1500
1206 1205
1192 1191
702 703
1412 1411
1060 1061
470 469
707 708
1133 1132
166 165
1197 1196
1215 1214
1030 1031
362 363
4 3
1167 1168
793 794
1418 1417
1195 1196
644 645
721 722
590 591
828 827
421 422
580 579
1186 1187
194 193
553 552
1430 1431
972 973
1398 1397
354 353
913 914
544 545
586 ...

output:

332021746

result:

ok 1 number(s): "332021746"

Test #14:

score: 5
Accepted
time: 125ms
memory: 252928kb

input:

59
1500
1206 1205
1192 1191
702 703
1412 1411
1060 1061
470 469
707 708
1133 1132
166 165
1197 1196
1215 1214
1030 1031
362 363
4 3
1167 1168
793 794
1418 1417
1195 1196
644 645
721 722
590 591
828 827
421 422
580 579
1186 1187
194 193
553 552
1430 1431
972 973
1398 1397
354 353
913 914
544 545
586 ...

output:

458452660

result:

ok 1 number(s): "458452660"

Test #15:

score: 5
Accepted
time: 117ms
memory: 252928kb

input:

109
1500
1205 1206
1191 1192
703 701
1411 1412
1061 1059
469 470
708 707
1131 1133
165 166
1195 1197
1213 1215
1031 1029
363 361
3 4
1168 1167
794 793
1417 1418
1196 1195
645 643
722 721
591 589
827 828
422 421
579 580
1187 1185
193 194
551 553
1431 1429
973 971
1397 1398
353 354
914 913
545 543
587...

output:

550433177

result:

ok 1 number(s): "550433177"

Test #16:

score: 5
Accepted
time: 118ms
memory: 252800kb

input:

109
1500
1205 1206
1191 1192
703 701
1411 1412
1061 1059
469 470
708 707
1131 1133
165 166
1195 1197
1213 1215
1031 1029
363 361
3 4
1168 1167
794 793
1417 1418
1196 1195
645 643
722 721
591 589
827 828
422 421
579 580
1187 1185
193 194
551 553
1431 1429
973 971
1397 1398
353 354
914 913
545 543
587...

output:

590770405

result:

ok 1 number(s): "590770405"

Test #17:

score: 5
Accepted
time: 121ms
memory: 252928kb

input:

109
1500
1205 1206
1191 1192
703 701
1411 1412
1061 1059
469 470
708 707
1131 1133
165 166
1195 1197
1213 1215
1031 1029
363 361
3 4
1168 1167
794 793
1417 1418
1196 1195
645 643
722 721
591 589
827 828
422 421
579 580
1187 1185
193 194
551 553
1431 1429
973 971
1397 1398
353 354
914 913
545 543
587...

output:

557926200

result:

ok 1 number(s): "557926200"

Test #18:

score: 5
Accepted
time: 123ms
memory: 252928kb

input:

109
1500
1205 1206
1191 1192
703 701
1411 1412
1061 1059
469 470
708 707
1131 1133
165 166
1195 1197
1213 1215
1031 1029
363 361
3 4
1168 1167
794 793
1417 1418
1196 1195
645 643
722 721
591 589
827 828
422 421
579 580
1187 1185
193 194
551 553
1431 1429
973 971
1397 1398
353 354
914 913
545 543
587...

output:

496374494

result:

ok 1 number(s): "496374494"

Test #19:

score: 5
Accepted
time: 197ms
memory: 347520kb

input:

2
2500
1205 1206
1191 1192
703 702
2396 2395
2401 2402
469 470
707 708
1133 1132
166 165
2390 2391
1214 1215
1031 1030
363 362
1651 1650
1736 1737
1980 1981
1417 1418
1196 1195
645 644
722 721
1577 1576
1557 1558
422 421
2320 2319
1186 1187
1984 1983
552 553
1689 1688
973 972
1398 1397
354 353
914 9...

output:

155139106

result:

ok 1 number(s): "155139106"

Test #20:

score: 5
Accepted
time: 199ms
memory: 488576kb

input:

6
3500
3187 3188
1191 1192
703 702
3099 3100
2401 2402
470 469
707 708
3230 3231
165 166
2390 2391
1215 1214
1031 1030
362 363
3239 3240
1736 1737
3339 3338
1417 1418
1196 1195
644 645
2975 2974
1577 1576
2757 2756
422 421
2319 2320
1187 1186
1983 1984
3141 3142
1689 1688
973 972
3019 3020
3169 3170...

output:

21222413

result:

ok 1 number(s): "21222413"

Extra Test:

score: 0
Extra Test Passed