QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#291139 | #6223. 神经网络 | MoRanSky | 100 ✓ | 197ms | 307508kb | C++23 | 3.3kb | 2023-12-26 05:02:17 | 2023-12-26 05:02:17 |
Judging History
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