QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#410714#6223. 神经网络Max_s_xaM100 ✓486ms481744kbC++174.7kb2024-05-14 11:45:302024-05-14 11:45:31

Judging History

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

  • [2024-05-14 11:45:31]
  • 评测
  • 测评结果:100
  • 用时:486ms
  • 内存:481744kb
  • [2024-05-14 11:45:30]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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