QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#657876#9488. Do Not Turn Backucup-team1264#AC ✓2601ms5628kbC++201.7kb2024-10-19 15:37:172024-10-19 15:37:17

Judging History

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

  • [2024-10-19 15:37:17]
  • 评测
  • 测评结果：AC
  • 用时：2601ms
  • 内存：5628kb
查看
  • [2024-10-19 15:37:17]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;

constexpr i64 MOD = 998244353;
constexpr int L = 300;
using Mat = array<array<int, L>, L>;

Mat matMul(Mat a, Mat b) {
    Mat res{};
    for (int i = 0; i < L; i++) {
        for (int k = 0; k < L; k++) {
            for (int j = 0; j < L; j++) {
                res[i][j] += i64(a[i][k]) * b[k][j] % MOD;
                if (res[i][j] >= MOD) res[i][j] -= MOD;
            }
        }
    }
    return res;
}

void debug(Mat a, int n) {
    for (int i = 0; i < 2 * n; i++) {
        for (int j = 0; j < 2 * n; j++) {
            cout << a[i][j];
            if (j != 2 * n - 1) cout << ", ";
        }
        cout << ";\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k; cin >> n >> m >> k;
    Mat trans{};
    Mat w0{};
    vector<int> deg(n);
    while (m--) {
        int u, v; cin >> u >> v;
        u--, v--;
        trans[u][v]++;
        trans[v][u]++;
        deg[u]++, deg[v]++;
    }
    for (int u = 0; u < n; u++) {
        trans[u + n][u] = (MOD - deg[u]) % MOD;
        trans[u][n + u] = 1;
        trans[u + n][u + n + n] = 1;
        trans[u + n + n][u + n] = 1;
        w0[u][u] = 1;
    }
    for (int u = 0; u < n; u++) {
        for (int v = 0; v < n; v++) {
            trans[u + n + n][v] = trans[u][v];
        }
    }
    // debug(w0, n);
    // debug(trans, n);
    // debug(matMul(w0, trans), n);
    // debug(matMul(w0, matMul(trans, trans)), n);
    while (k) {
        if (k & 1) w0 = matMul(w0, trans);
        trans = matMul(trans, trans);
        k >>= 1;
    }
    cout << w0[0][n - 1] << endl;
}
源文件, 语言: C++20

详细

Test #1:

score: 100
Accepted
time: 225ms
memory: 5624kb

input:

6 8 5
1 2
1 3
2 3
2 4
3 5
4 5
4 6
5 6

output:

2

result:

ok "2"

Test #2:

score: 0
Accepted
time: 897ms
memory: 5620kb

input:

11 11 2023
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
1 11

output:

1

result:

ok "1"

Test #3:

score: 0
Accepted
time: 1927ms
memory: 5388kb

input:

7 21 1000000000
1 2
1 3
1 4
1 5
1 6
1 7
2 3
2 4
2 5
2 6
2 7
3 4
3 5
3 6
3 7
4 5
4 6
4 7
5 6
5 7
6 7

output:

405422475

result:

ok "405422475"

Test #4:

score: 0
Accepted
time: 1757ms
memory: 5324kb

input:

12 56 78144853
1 2
1 3
1 4
1 6
1 7
1 9
1 10
1 11
1 12
2 4
2 5
2 6
2 8
2 9
2 10
2 11
2 12
3 4
3 5
3 6
3 7
3 8
3 9
3 11
3 12
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 12
5 6
5 7
5 8
5 9
5 10
5 11
5 12
6 8
6 9
6 10
7 8
7 9
7 11
7 12
8 9
8 10
8 11
8 12
9 10
9 11
9 12
10 11
11 12

output:

843326021

result:

ok "843326021"

Test #5:

score: 0
Accepted
time: 2496ms
memory: 5276kb

input:

13 61 268435455
1 2
1 3
1 4
1 5
1 6
1 8
1 9
1 10
1 11
1 12
1 13
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 12
2 13
3 4
3 5
3 6
3 7
3 8
3 9
3 10
4 6
4 7
4 9
4 12
4 13
5 6
5 7
5 9
5 11
5 13
6 7
6 8
6 9
6 11
6 12
6 13
7 8
7 10
7 11
7 12
8 9
8 10
8 11
8 12
8 13
9 10
9 12
9 13
10 11
10 12
10 13
11 12
11 13
12 13

output:

69651169

result:

ok "69651169"

Test #6:

score: 0
Accepted
time: 2235ms
memory: 5428kb

input:

14 79 33554431
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
2 3
2 4
2 5
2 6
2 7
2 8
2 11
2 12
2 14
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
3 14
4 5
4 6
4 7
4 8
4 9
4 11
4 12
5 6
5 7
5 10
5 11
5 12
5 13
5 14
6 7
6 8
6 9
6 10
6 11
6 12
6 13
6 14
7 8
7 9
7 10
7 11
7 12
7 13
7 14
8 10
8 11
8...

output:

793621538

result:

ok "793621538"

Test #7:

score: 0
Accepted
time: 1914ms
memory: 5588kb

input:

15 92 439487671
1 2
1 3
1 5
1 7
1 8
1 9
1 10
1 11
1 13
1 14
1 15
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
2 14
2 15
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
3 14
3 15
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 12
4 13
4 14
4 15
5 7
5 8
5 10
5 11
5 12
5 13
5 14
6 7
6 8
6 9
6 10
6 11
6 12
6 13
6 14
6 1...

output:

196201187

result:

ok "196201187"

Test #8:

score: 0
Accepted
time: 1924ms
memory: 5620kb

input:

5 10 230391930
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

output:

552614127

result:

ok "552614127"

Test #9:

score: 0
Accepted
time: 2496ms
memory: 5280kb

input:

5 8 268435455
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5

output:

666456772

result:

ok "666456772"

Test #10:

score: 0
Accepted
time: 2312ms
memory: 5568kb

input:

6 13 67108863
1 2
1 3
1 4
1 5
2 4
2 5
2 6
3 4
3 5
3 6
4 5
4 6
5 6

output:

317571510

result:

ok "317571510"

Test #11:

score: 0
Accepted
time: 2316ms
memory: 5336kb

input:

7 18 67108863
1 2
1 3
1 4
1 5
1 6
1 7
2 3
2 4
2 5
2 6
2 7
3 5
3 6
4 5
4 6
4 7
5 6
6 7

output:

921436359

result:

ok "921436359"

Test #12:

score: 0
Accepted
time: 1700ms
memory: 5328kb

input:

11 43 115349891
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
2 3
2 6
2 7
2 8
2 9
2 11
3 4
3 5
3 8
3 9
3 10
4 5
4 6
4 7
4 8
4 9
4 11
5 6
5 7
5 9
5 10
5 11
6 7
6 9
6 10
6 11
7 8
7 9
7 10
7 11
8 9
8 11
9 10
9 11

output:

853336717

result:

ok "853336717"

Test #13:

score: 0
Accepted
time: 2018ms
memory: 5396kb

input:

14 78 758166229
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
2 3
2 4
2 5
2 6
2 7
2 8
2 10
2 11
2 14
3 5
3 6
3 7
3 8
3 9
3 10
3 11
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 13
4 14
5 6
5 7
5 8
5 9
5 10
5 11
5 13
5 14
6 7
6 8
6 9
6 10
6 11
6 12
6 14
7 8
7 9
7 10
7 11
7 12
7 13
7 14
8 9
8 10
8 11
8 1...

output:

949739691

result:

ok "949739691"

Test #14:

score: 0
Accepted
time: 1920ms
memory: 5428kb

input:

52 51 376665160
1 2
1 3
2 4
4 5
5 6
5 7
3 8
5 9
5 10
5 11
6 12
4 13
2 14
6 15
14 16
9 17
8 18
15 19
11 20
9 21
1 22
21 23
3 24
24 25
24 26
10 27
7 28
24 29
16 30
6 31
4 32
5 33
10 34
33 35
32 36
19 37
29 38
18 39
17 40
13 41
39 42
3 43
12 44
34 45
20 46
38 47
27 48
43 49
5 50
6 51
4 52

output:

0

result:

ok "0"

Test #15:

score: 0
Accepted
time: 179ms
memory: 5340kb

input:

29 28 4
1 2
1 3
2 4
1 5
3 6
3 7
6 8
4 9
3 10
6 11
10 12
4 13
3 14
9 15
6 16
14 17
16 18
11 19
19 20
8 21
6 22
18 23
18 24
3 25
2 26
8 27
1 28
8 29

output:

1

result:

ok "1"

Test #16:

score: 0
Accepted
time: 2222ms
memory: 5324kb

input:

99 98 33554431
46 94
29 46
29 75
50 75
50 61
6 61
6 10
10 49
38 49
38 86
37 86
37 66
31 66
31 71
41 71
41 67
22 67
22 52
52 62
62 74
74 89
53 89
53 91
69 91
40 69
40 97
45 97
9 45
9 18
18 23
23 25
25 43
43 92
3 92
3 5
5 28
28 58
19 58
17 19
17 80
4 80
4 56
24 56
21 24
1 21
1 95
51 95
36 51
36 96
20 ...

output:

0

result:

ok "0"

Test #17:

score: 0
Accepted
time: 135ms
memory: 5324kb

input:

98 97 2
1 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
2 14
2 15
2 16
2 17
2 18
2 19
2 20
2 21
2 22
2 23
2 24
2 25
2 26
2 27
2 28
2 29
2 30
2 31
2 32
2 33
2 34
2 35
2 36
2 37
2 38
2 39
2 40
2 41
2 42
2 43
2 44
2 45
2 46
2 47
2 48
2 49
2 50
2 51
2 52
2 53
2 54
2 55
2 56
2 57
2 58
2 59
2 60
2 61
...

output:

1

result:

ok "1"

Test #18:

score: 0
Accepted
time: 1744ms
memory: 5572kb

input:

91 91 68838384
35 46
29 46
29 75
50 75
50 61
6 61
6 10
10 49
38 49
38 86
37 86
37 66
31 66
31 71
41 71
41 67
22 67
22 52
52 62
62 74
74 89
53 89
53 91
69 91
40 69
40 79
45 79
9 45
9 18
18 23
23 25
25 43
12 43
3 12
3 5
5 28
28 58
19 58
17 19
17 80
4 80
4 56
24 56
21 24
1 21
1 64
51 64
36 51
36 47
20 ...

output:

1

result:

ok "1"

Test #19:

score: 0
Accepted
time: 2064ms
memory: 5392kb

input:

92 92 860263916
30 45
45 60
60 66
66 78
15 78
9 15
9 14
14 35
35 37
37 85
24 85
24 65
64 65
10 64
10 53
32 53
22 32
22 51
51 80
80 92
77 92
43 77
33 43
33 39
39 82
6 82
2 6
2 88
40 88
40 58
25 58
25 72
72 91
7 91
7 8
8 57
48 57
21 48
21 68
68 79
55 79
12 55
12 38
1 38
1 90
63 90
13 63
13 44
44 54
47...

output:

1

result:

ok "1"

Test #20:

score: 0
Accepted
time: 1970ms
memory: 5628kb

input:

91 4095 412854823
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
...

output:

309435713

result:

ok "309435713"

Test #21:

score: 0
Accepted
time: 2324ms
memory: 5620kb

input:

92 4186 67108863
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1...

output:

445773689

result:

ok "445773689"

Test #22:

score: 0
Accepted
time: 2591ms
memory: 5592kb

input:

93 4278 536870911
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
...

output:

664971360

result:

ok "664971360"

Test #23:

score: 0
Accepted
time: 2187ms
memory: 5628kb

input:

94 4371 531304381
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
...

output:

33852961

result:

ok "33852961"

Test #24:

score: 0
Accepted
time: 1790ms
memory: 5628kb

input:

10 38 187055368
1 2
1 3
1 5
1 6
1 8
1 9
1 10
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
3 4
3 5
3 6
3 7
3 8
3 9
3 10
4 5
4 6
4 7
4 8
4 9
5 7
5 8
5 9
5 10
6 7
6 8
6 9
6 10
7 8
7 10
8 10

output:

174346166

result:

ok "174346166"

Test #25:

score: 0
Accepted
time: 1879ms
memory: 5340kb

input:

31 395 508956048
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 12
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 23
1 24
1 25
1 26
1 27
1 28
1 30
1 31
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
2 14
2 16
2 17
2 18
2 19
2 20
2 22
2 23
2 24
2 25
2 26
2 27
2 28
2 29
2 30
2 31
3 4
3 5
3 7
3 8
3 9
3 10
3 11
3 1...

output:

898454226

result:

ok "898454226"

Test #26:

score: 0
Accepted
time: 1739ms
memory: 5392kb

input:

46 843 103688348
1 2
1 3
1 4
1 5
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 33
1 34
1 35
1 36
1 37
1 38
1 41
1 42
1 43
1 44
1 45
2 3
2 4
2 5
2 6
2 7
2 9
2 10
2 11
2 12
2 13
2 14
2 15
2 16
2 18
2 19
2 20
2 22
2 23
2 26
2...

output:

804037438

result:

ok "804037438"

Test #27:

score: 0
Accepted
time: 2601ms
memory: 5360kb

input:

81 2612 536870911
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 21
1 22
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 49
1 50
1 51
1 52
1 53
1 55
1 56
1 57
1 58
1 59
1 60
1 61
1 63
1 64
1 65
...

output:

439960927

result:

ok "439960927"

Test #28:

score: 0
Accepted
time: 2412ms
memory: 5332kb

input:

98 3845 134217727
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 13
1 15
1 16
1 17
1 18
1 20
1 21
1 22
1 23
1 24
1 26
1 27
1 30
1 32
1 33
1 34
1 35
1 38
1 40
1 41
1 42
1 44
1 45
1 46
1 48
1 49
1 50
1 51
1 52
1 53
1 56
1 57
1 58
1 59
1 60
1 61
1 62
1 63
1 64
1 65
1 66
1 67
1 68
1 69
1 71
1 72
1 74
1 75
...

output:

687576024

result:

ok "687576024"

Test #29:

score: 0
Accepted
time: 2229ms
memory: 5620kb

input:

38 559 33554431
1 2
1 3
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 14
1 15
1 16
1 18
1 20
1 21
1 23
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 38
2 4
2 5
2 6
2 8
2 9
2 10
2 11
2 12
2 13
2 14
2 15
2 16
2 18
2 19
2 20
2 21
2 22
2 24
2 25
2 26
2 28
2 29
2 30
2 31
2 32
2 34
3 4
3 5
3 6
3 7
3 8
3 9
3...

output:

245031029

result:

ok "245031029"

Test #30:

score: 0
Accepted
time: 2501ms
memory: 5400kb

input:

53 1106 268435455
1 2
1 3
1 4
1 5
1 6
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
2 3
2 4
2 5
2 6
2 7
2 9
2 10
2 11
2 13
2 14
...

output:

437352844

result:

ok "437352844"

Test #31:

score: 0
Accepted
time: 2047ms
memory: 5276kb

input:

43 725 710015779
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 14
1 15
1 16
1 18
1 19
1 20
1 23
1 24
1 26
1 27
1 28
1 29
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 39
1 40
1 41
1 42
1 43
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 13
2 14
2 15
2 16
2 17
2 18
2 19
2 20
2 21
2 23
2 24
2 26
2 27
2 29
2 32
2 3...

output:

287707534

result:

ok "287707534"

Test #32:

score: 0
Accepted
time: 2327ms
memory: 5336kb

input:

66 1737 67108863
1 2
1 3
1 5
1 6
1 7
1 8
1 9
1 10
1 12
1 13
1 15
1 16
1 17
1 18
1 21
1 22
1 23
1 24
1 25
1 26
1 31
1 32
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 45
1 46
1 47
1 49
1 50
1 51
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 61
1 62
1 63
1 64
1 66
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2...

output:

655903832

result:

ok "655903832"

Test #33:

score: 0
Accepted
time: 1835ms
memory: 5428kb

input:

29 327 815825607
1 2
1 3
1 4
1 5
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 18
1 19
1 20
1 21
1 23
1 24
1 25
1 26
1 27
1 28
1 29
2 3
2 5
2 6
2 7
2 8
2 9
2 10
2 12
2 13
2 14
2 15
2 16
2 17
2 18
2 19
2 21
2 23
2 24
2 25
2 26
2 27
2 28
2 29
3 4
3 6
3 7
3 9
3 10
3 11
3 12
3 13
3 15
3 16
3 17
3 18
3 20
...

output:

3611745

result:

ok "3611745"

Test #34:

score: 0
Accepted
time: 2582ms
memory: 5388kb

input:

100 4950 536870911
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59...

output:

77654284

result:

ok "77654284"

Test #35:

score: 0
Accepted
time: 2586ms
memory: 5388kb

input:

100 3962 536870911
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 12
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 35
1 36
1 37
1 38
1 39
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 51
1 53
1 54
1 55
1 56
1 57
1 58
1 60
1 61
1 62
1 63
1 64
1 65
1 67...

output:

277610741

result:

ok "277610741"

Test #36:

score: 0
Accepted
time: 2595ms
memory: 5328kb

input:

99 3919 536870911
1 2
1 3
1 4
1 5
1 7
1 9
1 10
1 11
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 23
1 24
1 25
1 27
1 28
1 29
1 32
1 33
1 34
1 36
1 37
1 38
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 56
1 57
1 58
1 59
1 60
1 62
1 63
1 64
1 65
1 66
1 67
1 68
1 70
1 7...

output:

377999899

result:

ok "377999899"

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

服务器时间: 2024-12-05 11:21:04 | 开源项目