QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#657489#9488. Do Not Turn Backucup-team4474#AC ✓816ms4256kbC++141.3kb2024-10-19 14:51:072024-10-19 14:51:07

Judging History

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

  • [2024-10-19 14:51:07]
  • 评测
  • 测评结果：AC
  • 用时：816ms
  • 内存：4256kb
查看
  • [2024-10-19 14:51:07]
  • 提交

answer

#include<bits/stdc++.h>
#define p 998244353
using namespace std;
int n,m,k,b[100][100],bn[100];
int a[200][200],f[200];
int f1[100],f2[100];
int la[200][200],lf[200];
int dr()
{
	int xx=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')xx=xx*10+ch-'0',ch=getchar();
	return xx;
}
void workf()
{
	memset(lf,0,sizeof(lf));
	for(int i=0;i<2*n;i++)for(int j=0;j<2*n;j++)lf[j]=(lf[j]+1ll*f[i]*a[i][j])%p;
	for(int i=0;i<2*n;i++)f[i]=lf[i];
}
void worka()
{
	memset(la,0,sizeof(la));
	for(int i=0;i<2*n;i++)for(int j=0;j<2*n;j++)for(int o=0;o<2*n;o++)la[i][j]=(la[i][j]+1ll*a[i][o]*a[o][j])%p;
	for(int i=0;i<2*n;i++)for(int j=0;j<2*n;j++)a[i][j]=la[i][j];
}
void cal(int t)
{
	for(;t;t>>=1)
	{
		if(t&1)workf();
		worka();
	}
}
int main()
{
	n=dr(),m=dr(),k=dr();
	for(int i=1;i<=m;i++)
	{
		int u=dr()-1,v=dr()-1;
		b[u][v]=b[v][u]=1,++bn[u],++bn[v];
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)a[j][i]=b[j][i];
		a[i][n+i]=1,a[n+i][i]=p-bn[i]+1;
	}
	for(int i=0;i<n;i++)if(b[0][i])f1[i]=1;
	for(int i=0;i<n;i++)if(f1[i])
	for(int j=1;j<n;j++)if(b[i][j])f2[j]+=f1[i];
	if(k==1)printf("%d",f1[n-1]);
	else if(k==2)printf("%d",f2[n-1]);
	else
	{
		for(int i=0;i<n;i++)f[i]=f2[i],f[n+i]=f1[i];
		cal(k-2);
		printf("%d",f[n-1]);
	}
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 4040kb

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: 1ms
memory: 4016kb

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: 1ms
memory: 3964kb

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: 2ms
memory: 3976kb

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: 2ms
memory: 4104kb

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: 0ms
memory: 3996kb

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: 3ms
memory: 3992kb

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: 1ms
memory: 4084kb

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: 1ms
memory: 3980kb

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: 0ms
memory: 3960kb

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: 1ms
memory: 4024kb

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: 1ms
memory: 4028kb

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: 2ms
memory: 3984kb

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: 112ms
memory: 4108kb

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: 2ms
memory: 4072kb

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: 682ms
memory: 4148kb

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: 1ms
memory: 4024kb

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: 573ms
memory: 4212kb

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: 658ms
memory: 4192kb

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: 616ms
memory: 4192kb

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: 570ms
memory: 4252kb

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: 658ms
memory: 4252kb

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: 679ms
memory: 4136kb

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: 1ms
memory: 4028kb

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: 23ms
memory: 4088kb

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: 72ms
memory: 4100kb

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: 429ms
memory: 4172kb

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: 719ms
memory: 4140kb

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: 37ms
memory: 4108kb

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: 115ms
memory: 4048kb

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: 65ms
memory: 4040kb

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: 208ms
memory: 4136kb

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: 20ms
memory: 4084kb

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: 812ms
memory: 4216kb

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: 816ms
memory: 4256kb

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: 797ms
memory: 4220kb

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 繁體中文 简体中文

Server Time: 2024-12-12 23:14:43 | OpenSource Project