QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#410714 | #6223. 神经网络 | Max_s_xaM | 100 ✓ | 486ms | 481744kb | C++17 | 4.7kb | 2024-05-14 11:45:30 | 2024-05-14 11:45:31 |
Judging History
answer
#include <iostream>
#include <vector>
typedef long long ll;
typedef double lf;
// #define DEBUG 1
struct IO
{
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
char buf[MAXSIZE], *p1, *p2;
char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
IO() : p1(buf), p2(buf), pp(pbuf) {}
~IO() {fwrite(pbuf, 1, pp - pbuf, stdout);}
#endif
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) ? ' ' : *p1++)
#define blank(x) (x == ' ' || x == '\n' || x == '\r' || x == '\t')
template <typename T>
void Read(T &x)
{
#if DEBUG
std::cin >> x;
#else
bool sign = 0; char ch = gc(); x = 0;
for (; !isdigit(ch); ch = gc())
if (ch == '-') sign = 1;
for (; isdigit(ch); ch = gc()) x = x * 10 + (ch ^ 48);
if (sign) x = -x;
#endif
}
void Read(char *s)
{
#if DEBUG
std::cin >> s;
#else
char ch = gc();
for (; blank(ch); ch = gc());
for (; !blank(ch); ch = gc()) *s++ = ch;
*s = 0;
#endif
}
void Read(char &c) {for (c = gc(); blank(c); c = gc());}
void Push(const char &c)
{
#if DEBUG
putchar(c);
#else
if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
*pp++ = c;
#endif
}
template <typename T>
void Write(T x)
{
if (x < 0) x = -x, Push('-');
static T sta[35];
int top = 0;
do sta[top++] = x % 10, x /= 10; while (x);
while (top) Push(sta[--top] ^ 48);
}
template <typename T>
void Write(T x, char lst) {Write(x), Push(lst);}
} IO;
#define Read(x) IO.Read(x)
#define Write(x, y) IO.Write(x, y)
#define Put(x) IO.Push(x)
using namespace std;
const int MAXN = 5010, MAXM = 310, mod = 998244353;
int n, m, N[MAXM];
ll S[MAXN][MAXN], fac[MAXN];
ll dp[MAXM][MAXN], h[MAXN];
vector <int> e[MAXN];
ll f[MAXN][MAXN][4], g[MAXN][4];
int sz[MAXN];
void DFS(int u, int fa)
{
sz[u] = 1;
f[u][1][0] = f[u][1][1] = f[u][1][2] = 0;
f[u][1][3] = 1;
for (auto v : e[u])
{
if (v == fa) continue;
DFS(v, u);
for (int i = 1; i <= sz[u] + sz[v]; i++) g[i][0] = g[i][1] = g[i][2] = g[i][3] = 0;
for (int i = sz[u]; i; i--)
for (int j = sz[v]; j; j--)
{
for (int x = 0; x < 4; x++)
for (int y = 0; y < 4; y++)
{
g[i + j][x] = (g[i + j][x] + f[u][i][x] * f[v][j][y]) % mod;
if ((x == 1 || x == 3) && (y == 2 || y == 3))
g[i + j - 1][x == 3 ? 2 : 0] = (g[i + j - 1][x == 3 ? 2 : 0] + f[u][i][x] * f[v][j][y]) % mod;
if ((x == 2 || x == 3) && (y == 1 || y == 3))
g[i + j - 1][x == 3 ? 1 : 0] = (g[i + j - 1][x == 3 ? 1 : 0] + f[u][i][x] * f[v][j][y]) % mod;
}
}
sz[u] += sz[v];
for (int i = 1; i <= sz[u] + sz[v]; i++)
for (int j = 0; j < 4; j++)
f[u][i][j] = g[i][j];
}
}
int main()
{
// freopen("B.in", "r", stdin);
// freopen("B.out", "w", stdout);
#if DEBUG
#else
ios::sync_with_stdio(0), cin.tie(0);
#endif
S[1][1] = 1;
for (int i = 2; i < MAXN; i++)
for (int j = 1; j <= i; j++)
S[i][j] = (S[i - 1][j - 1] + S[i - 1][j] * (i + j - 1) % mod) % mod;
fac[0] = 1;
for (int i = 1; i < MAXN; i++) fac[i] = fac[i - 1] * i % mod;
Read(m);
for (int t = 1; t <= m; t++)
{
Read(n); N[t] = n;
for (int i = 1; i <= n; i++) e[i].clear();
for (int i = 1, u, v; i < n; i++) Read(u), Read(v), e[u].push_back(v), e[v].push_back(u);
DFS(1, 0);
for (int i = 1; i <= n; i++) f[1][i][0] = (f[1][i][0] + f[1][i][1] + f[1][i][2] + f[1][i][3]) % mod;
for (int i = 1; i <= n; i++)
for (int j = n - i; j < n; j++)
dp[t][j] = (dp[t][j] + f[1][i][0] * S[i][n - j] % mod * ((n - i) & 1 ? -1 : 1)) % mod;
}
for (int t = 2; t <= m; t++)
{
for (int i = 0; i < N[t - 1] + N[t]; i++) h[i] = 0;
for (int i = N[t - 1] - 1; ~i; i--)
for (int j = N[t] - 1; ~j; j--)
h[i + j] = (h[i + j] + dp[t - 1][i] * dp[t][j]) % mod;
N[t] += N[t - 1];
for (int i = 0; i < N[t]; i++) dp[t][i] = h[i];
}
ll ans = 0;
for (int i = 0; i < N[m]; i++)
ans = (ans + dp[m][i] * fac[N[m] - i - 1] % mod * (i & 1 ? -1 : 1)) % mod;
cout << (ans + mod) % mod << '\n';
return 0;
}
詳細信息
Test #1:
score: 5
Accepted
time: 23ms
memory: 120880kb
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: 28ms
memory: 120764kb
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: 28ms
memory: 122536kb
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: 44ms
memory: 122700kb
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: 28ms
memory: 122616kb
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: 31ms
memory: 122672kb
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: 33ms
memory: 121840kb
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: 35ms
memory: 121676kb
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: 31ms
memory: 121736kb
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: 23ms
memory: 121764kb
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: 233ms
memory: 199884kb
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: 240ms
memory: 199920kb
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: 228ms
memory: 199888kb
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: 238ms
memory: 199932kb
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: 246ms
memory: 201396kb
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: 223ms
memory: 201292kb
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: 229ms
memory: 201232kb
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: 250ms
memory: 201208kb
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: 486ms
memory: 325716kb
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: 468ms
memory: 481744kb
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