QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#291139#6223. 神经网络MoRanSky100 ✓197ms307508kbC++233.3kb2023-12-26 05:02:172023-12-26 05:02:17

Judging History

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

  • [2023-12-26 05:02:17]
  • 评测
  • 测评结果:100
  • 用时:197ms
  • 内存:307508kb
  • [2023-12-26 05:02:17]
  • 提交

answer

// Skyqwq
#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 5005, P = 998244353;

int m, n, f[N][N][3], sz[N], h[N][3], G[N], C[N][N], H[N], fact[N], infact[N], inv[N], F[N], B[N];

vector<int> g[N];

void inline clr() {
	for (int i = 1; i <= n; i++) g[i].clear();
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			f[i][j][0] = f[i][j][1] = f[i][j][2] = 0;
		}
	}
}

void inline add(int &x, int y) {
	x += y;
	if (x >= P) x -= P;
}

void merge(int u, int v) {
	int A = sz[u], B = sz[v], C = sz[u] + sz[v];
	for (int i = 1; i <= C; i++)
		h[i][0] = h[i][1] = h[i][2] = 0;
	for (int i = 1; i <= A; i++) {
		for (int j = 1; j <= B; j++) {
			for (int x = 0; x < 3; x++) {
				for (int y = 0; y < 3; y++) {
					add(h[i + j][x], 1ll * f[u][i][x] * f[v][j][y] % P * (y == 2 ? 2 : 1) % P);
					if (x >= 2 && y) add(h[i + j - 1][0], 1ll * f[u][i][x] * f[v][j][y] % P * 2 % P);
					if (x == 1 && y) add(h[i + j - 1][2], 1ll * f[u][i][x] * f[v][j][y] % P);
				}
			}
		}
	}
	
	for (int i = 1; i <= C; i++)
		f[u][i][0] = h[i][0], f[u][i][1] = h[i][1], f[u][i][2] = h[i][2];
	sz[u] += sz[v];
}

void dfs(int u, int la) {
	f[u][1][1] = 1;
	sz[u] = 1;
	for (int v: g[u]) {
		if (v == la) continue;
		dfs(v, u);
		merge(u, v);
	}
}

void inline prework() {
	inv[1] = 1;
	for (int i = 2; i < N; i++)
		inv[i] = (P - (LL)P / i) * inv[P % i] % P;
	fact[0] = infact[0] = 1;
	for (int i = 1; i < N; i++) {
		fact[i] = 1ll * fact[i - 1] * i % P;
		infact[i] = 1ll * infact[i - 1] * inv[i] % P;
	}
	C[0][0] = 1;
	for (int i = 1; i < N; i++) {
		C[i][0] = 1;
		for (int j = 1; j <= i; j++)
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % P;
	}
}

int inline A(int x) {
	return (x & 1) ? P - 1 : 1;
}

int inline power(int a, int b) {
	int res = 1;
	while (b) {
		if (b & 1) res = 1ll * res * a % P;
		a = 1ll * a * a % P;
		b >>= 1;
	}
	return res;
}

int main() {
	prework();
	read(m);
	F[0] = 1;
	int S = 0;
	while (m--) {
		read(n);
		for (int i = 1, u, v; i < n; i++)
			read(u), read(v), g[u].pb(v), g[v].pb(u);
		dfs(1, 0);		
		for (int i = 1; i <= n; i++) G[i] = 0, H[i] = 0;
		for (int i = 1; i <= n; i++) {
			add(G[i], f[1][i][0]);
			add(G[i], f[1][i][1]);
			add(G[i], 1ll * f[1][i][2] * 2 % P);
		}
		for (int i = 1; i <= n; i++) {
			for (int j = i; j <= n; j++) {
				add(H[i], 1ll * G[j] * fact[j] % P * C[j - 1][j - i] % P * A(j - i) % P);
			}
		}
		for (int i = 0; i <= S; i++) B[i] = F[i], F[i] = 0;
		for (int i = 0; i <= S; i++) {
			for (int j = 1; j <= n; j++) {
				add(F[i + j], 1ll * B[i] * H[j] % P * infact[j] % P);
			}
		}
		S += n;
		clr();
	}
	int ans = 0;
	for (int i = 1; i <= S; i++) add(ans, 1ll * F[i] * fact[i - 1] % P);
	printf("%d\n", ans);
    return 0;
}


详细

Test #1:

score: 5
Accepted
time: 0ms
memory: 102648kb

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: 4ms
memory: 102608kb

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: 4ms
memory: 102580kb

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

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: 8ms
memory: 102400kb

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: 4ms
memory: 102164kb

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: 11ms
memory: 104656kb

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: 12ms
memory: 104532kb

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

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: 11ms
memory: 104660kb

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: 111ms
memory: 190628kb

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: 106ms
memory: 190656kb

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: 99ms
memory: 190648kb

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: 106ms
memory: 188784kb

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: 101ms
memory: 190412kb

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: 101ms
memory: 190424kb

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: 94ms
memory: 190772kb

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: 101ms
memory: 190768kb

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: 195ms
memory: 248064kb

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: 197ms
memory: 307508kb

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