QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#657489 | #9488. Do Not Turn Back | ucup-team4474# | AC ✓ | 816ms | 4256kb | C++14 | 1.3kb | 2024-10-19 14:51:07 | 2024-10-19 14:51:07 |
Judging History
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]);
}
}
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