QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#790862	#9488. Do Not Turn Back	k1nsom^#	RE	1236ms	59080kb	C++14	2.1kb	2024-11-28 15:44:40	2024-11-28 15:44:45

Judging History

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

[2024-11-28 15:44:45]
评测

测评结果：RE
用时：1236ms
内存：59080kb

查看

[2024-11-28 15:44:40]
提交

answer

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 8005, mod = 998244353;
int n, m, s, t, x[N], y[N], cnt;
int T, A[N][N], re[N][N], mtx[N][N], tmp[N][N];
void pow(int y)
{
    for (int i = 1; i <= cnt; i++)
        for (int j = 1; j <= cnt; j++)
            if (i == j)
                re[i][j] = 1;
            else
                re[i][j] = 0;
    while (y)
    {
        if (y & 1)
        {
            for (int i = 1; i <= cnt; i++)
                for (int j = 1; j <= cnt; j++)
                    tmp[i][j] = 0;
            for (int i = 1; i <= cnt; i++)
                for (int j = 1; j <= cnt; j++)
                    for (int k = 1; k <= cnt; k++)
                        tmp[i][j] = (tmp[i][j] + re[i][k] * mtx[k][j] % mod) % mod;
            for (int i = 1; i <= cnt; i++)
                for (int j = 1; j <= cnt; j++)
                    re[i][j] = tmp[i][j];
        }
        y >>= 1;
        for (int i = 1; i <= cnt; i++)
            for (int j = 1; j <= cnt; j++)
                tmp[i][j] = 0;
        for (int i = 1; i <= cnt; i++)
            for (int j = 1; j <= cnt; j++)
                for (int k = 1; k <= cnt; k++)
                    tmp[i][j] = (tmp[i][j] + mtx[i][k] * mtx[k][j] % mod) % mod;
        for (int i = 1; i <= cnt; i++)
            for (int j = 1; j <= cnt; j++)
                mtx[i][j] = tmp[i][j];
    }
}
signed main()
{
    cin >> n >> m >> T;
    s = 1, t = n;
    x[++cnt] = 0, y[cnt] = s;
    for (int i = 1, u, v; i <= m; i++)
    {
        cin >> u >> v;
        x[++cnt] = u, y[cnt] = v;
        x[++cnt] = v, y[cnt] = u;
    }
    for (int i = 1; i <= cnt; i++)
        for (int j = 1; j <= cnt; j++)
            if (i != j && i != (j ^ 1))
            {
                if (y[i] == x[j])
                    A[i][j] = 1;
            }
    for (int i = 1; i <= cnt; i++)
        for (int j = 1; j <= cnt; j++)
            mtx[i][j] = A[i][j];
    pow(T);
    int ans = 0;
    for (int i = 1; i <= cnt; i++)
        if (y[i] == t)
            ans = (ans + re[1][i]) % mod;
    cout << ans << endl;
    return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 2ms

memory: 13872kb

input:

output:

result:

ok "2"

Test #2:

score: 0

Accepted

time: 0ms

memory: 18080kb

input:

output:

result:

ok "1"

Test #3:

score: 0

Accepted

time: 10ms

memory: 20012kb

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: 182ms

memory: 38528kb

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: 331ms

memory: 40592kb

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: 648ms

memory: 50796kb

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: 876ms

memory: 56944kb

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: 3ms

memory: 13860kb

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: 0ms

memory: 13872kb

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: 3ms

memory: 17996kb

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: 7ms

memory: 20068kb

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: 81ms

memory: 32516kb

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: 562ms

memory: 48796kb

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: 147ms

memory: 34352kb

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:

result:

ok "0"

Test #15:

score: 0

Accepted

time: 3ms

memory: 24260kb

input:

output:

result:

ok "1"

Test #16:

score: 0

Accepted

time: 1236ms

memory: 59080kb

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:

result:

ok "0"

Test #17:

score: 0

Accepted

time: 71ms

memory: 59016kb

input:

output:

result:

ok "1"

Test #18:

score: 0

Accepted

time: 776ms

memory: 57024kb

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:

result:

ok "1"

Test #19:

score: 0

Accepted

time: 944ms

memory: 54852kb

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:

result:

ok "1"

Test #20:

score: -100

Runtime Error

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
...