QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#341088#6223. 神经网络DaiRuiChen007100 ✓183ms396196kbC++172.3kb2024-02-29 15:33:222024-02-29 15:33:23

Judging History

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

  • [2024-02-29 15:33:23]
  • 评测
  • 测评结果:100
  • 用时:183ms
  • 内存:396196kb
  • [2024-02-29 15:33:22]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5005,MOD=998244353;
int fac[MAXN],ifac[MAXN];
int ksm(int a,int b=MOD-2,int p=MOD) {
	int ret=1;
	for(;b;a=1ll*a*a%p,b>>=1) if(b&1) ret=1ll*ret*a%p;
	return ret;
}
int C[MAXN][MAXN],co[MAXN][MAXN];
//co: i element -> j set
vector <int> G[MAXN];
int f[MAXN][MAXN],g[MAXN][MAXN],h[MAXN][MAXN]; //deg = 0,1,2
int tf[MAXN],tg[MAXN],th[MAXN],siz[MAXN];
void dfs(int u,int fz) {
	f[u][0]=1,siz[u]=1;
	for(int v:G[u]) if(v^fz) {
		dfs(v,u);
		memset(tf,0,sizeof(tf));
		memset(tg,0,sizeof(tg));
		memset(th,0,sizeof(th));
		for(int i=0;i<=siz[u];++i) for(int j=0;j<=siz[v];++j) {
			int x=(f[v][j]+2ll*g[v][j]+2ll*h[v][j])%MOD;
			tf[i+j+1]=(tf[i+j+1]+1ll*f[u][i]*x)%MOD;
			tg[i+j+1]=(tg[i+j+1]+1ll*g[u][i]*x)%MOD;
			th[i+j+1]=(th[i+j+1]+1ll*h[u][i]*x)%MOD;
			tg[i+j]=(tg[i+j]+1ll*f[u][i]*(f[v][j]+g[v][j]))%MOD;
			th[i+j]=(th[i+j]+1ll*g[u][i]*(f[v][j]+g[v][j]))%MOD;
		}
		siz[u]+=siz[v];
		memcpy(f[u],tf,sizeof(f[u]));
		memcpy(g[u],tg,sizeof(g[u]));
		memcpy(h[u],th,sizeof(h[u]));
	}
}
int wys[MAXN],dp[MAXN],tdp[MAXN]; //dp to i elements
signed main() {
	for(int i=fac[0]=1;i<MAXN;++i) ifac[i]=ksm(fac[i]=1ll*fac[i-1]*i%MOD)%MOD;
	for(int i=0;i<MAXN;++i) for(int j=C[i][0]=1;j<=i;++j) C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
	for(int i=1;i<MAXN;++i) for(int j=1;j<=i;++j) co[i][j]=1ll*fac[i]*ifac[j]%MOD*C[i-1][j-1]%MOD;
	int n,m,tot=0; dp[0]=1;
	scanf("%d",&m);
	for(int t=1;t<=m;++t) {
		scanf("%d",&n);
		for(int i=1;i<=n;++i) {
			G[i].clear(),siz[i]=0;
			memset(f[i],0,sizeof(f[i]));
			memset(g[i],0,sizeof(g[i]));
			memset(h[i],0,sizeof(h[i]));
		}
		for(int i=1,u,v;i<n;++i) {
			scanf("%d%d",&u,&v);
			G[u].push_back(v),G[v].push_back(u);
		}
		dfs(1,0);
		memset(wys,0,sizeof(wys));
		for(int i=1;i<=n;++i) {
			int v=(f[1][i-1]+2ll*g[1][i-1]+2ll*h[1][i-1])%MOD;
			for(int j=i;j>=1;--j) {
				wys[j]=(wys[j]+((i-j)&1?-1ll:1ll)*v*co[i][j])%MOD;
			}
		}
		for(int i=1;i<=n;++i) if(wys[i]<0) wys[i]+=MOD;
		memset(tdp,0,sizeof(tdp));
		for(int i=0;i<=tot;++i) for(int j=1;j<=n;++j) {
			tdp[i+j]=(tdp[i+j]+1ll*dp[i]*wys[j])%MOD;
		}
		tot+=n;
		memcpy(dp,tdp,sizeof(dp));
	}
	int ans=0;
	for(int i=1;i<=tot;++i) ans=(ans+1ll*dp[i]*fac[i-1])%MOD;
	printf("%d\n",ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 5
Accepted
time: 43ms
memory: 170824kb

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: 42ms
memory: 171160kb

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: 21ms
memory: 170948kb

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: 27ms
memory: 170852kb

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: 43ms
memory: 170616kb

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: 35ms
memory: 174500kb

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: 52ms
memory: 173744kb

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: 55ms
memory: 173580kb

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: 43ms
memory: 173448kb

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: 44ms
memory: 182372kb

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: 140ms
memory: 259176kb

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: 132ms
memory: 269628kb

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: 130ms
memory: 272088kb

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: 148ms
memory: 273368kb

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: 143ms
memory: 276480kb

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: 129ms
memory: 286084kb

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: 142ms
memory: 284664kb

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: 125ms
memory: 285328kb

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: 183ms
memory: 342880kb

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: 171ms
memory: 396196kb

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