QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#245967 | #7766. 栞 | grass8cow | 100 ✓ | 41ms | 5972kb | C++14 | 1.3kb | 2023-11-10 14:52:15 | 2023-11-10 14:52:15 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int q[510],dp[510][510],c[510][510],jc[510],f[510],g[510];
int calc(int fi,int m){
int su=0;
for(int j=m;j<=fi;j++)(su+=(((j-m)&1)?-1ll:1ll)*c[j-1][m-1]*dp[fi][j]%mod)%=mod;
return su;
}
int n,m;
int main(){
//freopen("guide.in","r",stdin);
//freopen("guide.out","w",stdout);
scanf("%d%d",&n,&m);
c[0][0]=1;
for(int i=1;i<=n;i++){
c[i][0]=1;
for(int j=1;j<=i;j++)c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
}
bool fl=1;jc[0]=1;
for(int i=1;i<=n;i++)jc[i]=1ll*i*jc[i-1]%mod,
scanf("%d",&q[i]),fl&=(q[i]==i);
dp[0][0]=1;
for(int i=0;i<n;i++)for(int j=0;j<=i;j++)if(dp[i][j])
for(int k=i+1;k<=n;k++)
(dp[k][j+1]+=1ll*dp[i][j]*jc[k-i]%mod)%=mod;
if(fl){
int ans=0;
for(int i=m;i<=n;i++){
int su=0;
for(int j=i;j<=n;j++)
(su+=(((j-i)&1)?-1ll:1ll)*c[j-1][i-1]*dp[n][j]%mod)%=mod;
(ans+=su)%=mod;
}
printf("%d",(ans+mod)%mod);return 0;
}
int fi=-1;
for(int i=1;i<n;i++)if(q[i]>q[i+1]){if(fi==-1)fi=i;break;}
int ans=calc(fi,m-(n-fi));
int fr=n;
for(int i=fi+1;i<n;i++)if(q[i]>q[i+1]){fr=i;break;}
if(fr-fi>=2&&q[fi]<q[fi+2]){
for(int i=2;i<=fr-fi;i++)(ans+=1ll*jc[i-1]*calc(fi,m-(n-fi)+i-1)%mod)%=mod;
}
return printf("%d",(ans+mod)%mod),0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 0ms
memory: 3896kb
input:
6 1 1 2 3 4 5 6
output:
720
result:
ok 1 number(s): "720"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3912kb
input:
6 3 1 2 5 3 4 6
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
6 3 1 2 4 3 6 5
output:
3
result:
ok 1 number(s): "3"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
6 5 1 2 3 5 4 6
output:
4
result:
ok 1 number(s): "4"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
6 5 1 2 3 5 4 6
output:
4
result:
ok 1 number(s): "4"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3988kb
input:
6 4 1 3 2 4 6 5
output:
3
result:
ok 1 number(s): "3"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3900kb
input:
6 5 1 3 2 5 4 6
output:
2
result:
ok 1 number(s): "2"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
6 3 1 2 3 6 5 4
output:
13
result:
ok 1 number(s): "13"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3912kb
input:
6 4 1 2 5 4 3 6
output:
3
result:
ok 1 number(s): "3"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3912kb
input:
6 3 1 2 5 4 3 6
output:
0
result:
ok 1 number(s): "0"
Subtask #2:
score: 20
Accepted
Dependency #1:
100%
Accepted
Test #11:
score: 20
Accepted
time: 0ms
memory: 3928kb
input:
9 9 1 2 3 4 5 6 7 8 9
output:
1
result:
ok 1 number(s): "1"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
9 3 1 2 3 4 5 6 9 7 8
output:
3447
result:
ok 1 number(s): "3447"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
9 7 1 3 2 4 6 5 7 8 9
output:
3
result:
ok 1 number(s): "3"
Test #14:
score: 0
Accepted
time: 0ms
memory: 4004kb
input:
9 5 1 2 3 4 5 6 7 9 8
output:
531
result:
ok 1 number(s): "531"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
9 9 1 4 3 2 5 6 7 8 9
output:
1
result:
ok 1 number(s): "1"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
9 2 1 2 3 4 5 6 7 9 8
output:
29093
result:
ok 1 number(s): "29093"
Test #17:
score: 0
Accepted
time: 0ms
memory: 3860kb
input:
9 4 1 2 3 4 5 6 7 9 8
output:
2109
result:
ok 1 number(s): "2109"
Test #18:
score: 0
Accepted
time: 0ms
memory: 3912kb
input:
9 8 1 2 3 5 4 7 6 8 9
output:
4
result:
ok 1 number(s): "4"
Test #19:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
9 7 1 2 3 4 5 7 6 9 8
output:
23
result:
ok 1 number(s): "23"
Test #20:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
9 7 1 2 3 4 5 7 6 9 8
output:
23
result:
ok 1 number(s): "23"
Subtask #3:
score: 30
Accepted
Test #21:
score: 30
Accepted
time: 40ms
memory: 5820kb
input:
500 369 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...
output:
151242732
result:
ok 1 number(s): "151242732"
Test #22:
score: 0
Accepted
time: 36ms
memory: 5912kb
input:
500 261 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...
output:
175105582
result:
ok 1 number(s): "175105582"
Test #23:
score: 0
Accepted
time: 41ms
memory: 5888kb
input:
500 79 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...
output:
328555836
result:
ok 1 number(s): "328555836"
Test #24:
score: 0
Accepted
time: 39ms
memory: 5876kb
input:
500 306 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...
output:
738246233
result:
ok 1 number(s): "738246233"
Test #25:
score: 0
Accepted
time: 40ms
memory: 5812kb
input:
500 291 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...
output:
90157368
result:
ok 1 number(s): "90157368"
Test #26:
score: 0
Accepted
time: 36ms
memory: 5880kb
input:
500 268 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...
output:
582110163
result:
ok 1 number(s): "582110163"
Test #27:
score: 0
Accepted
time: 40ms
memory: 5808kb
input:
500 295 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...
output:
551109392
result:
ok 1 number(s): "551109392"
Test #28:
score: 0
Accepted
time: 40ms
memory: 5972kb
input:
500 137 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...
output:
709320534
result:
ok 1 number(s): "709320534"
Test #29:
score: 0
Accepted
time: 40ms
memory: 5896kb
input:
500 66 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...
output:
735053639
result:
ok 1 number(s): "735053639"
Test #30:
score: 0
Accepted
time: 40ms
memory: 5904kb
input:
500 233 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...
output:
676167049
result:
ok 1 number(s): "676167049"
Subtask #4:
score: 40
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #31:
score: 40
Accepted
time: 36ms
memory: 5972kb
input:
500 198 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...
output:
830163792
result:
ok 1 number(s): "830163792"
Test #32:
score: 0
Accepted
time: 36ms
memory: 5892kb
input:
500 432 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 80 78 79 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...
output:
409343845
result:
ok 1 number(s): "409343845"
Test #33:
score: 0
Accepted
time: 40ms
memory: 5884kb
input:
500 265 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...
output:
194041644
result:
ok 1 number(s): "194041644"
Test #34:
score: 0
Accepted
time: 39ms
memory: 5964kb
input:
500 173 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...
output:
526227080
result:
ok 1 number(s): "526227080"
Test #35:
score: 0
Accepted
time: 39ms
memory: 5880kb
input:
500 483 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...
output:
614441401
result:
ok 1 number(s): "614441401"
Test #36:
score: 0
Accepted
time: 40ms
memory: 5876kb
input:
500 243 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...
output:
284882224
result:
ok 1 number(s): "284882224"
Test #37:
score: 0
Accepted
time: 40ms
memory: 5876kb
input:
500 282 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...
output:
308933889
result:
ok 1 number(s): "308933889"
Test #38:
score: 0
Accepted
time: 36ms
memory: 5876kb
input:
500 231 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...
output:
131213230
result:
ok 1 number(s): "131213230"
Test #39:
score: 0
Accepted
time: 40ms
memory: 5880kb
input:
500 415 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 100 99 ...
output:
590026968
result:
ok 1 number(s): "590026968"
Test #40:
score: 0
Accepted
time: 40ms
memory: 5804kb
input:
500 344 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...
output:
124432123
result:
ok 1 number(s): "124432123"