QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #72144 | #4812. Counting Sequence | Appleblue17 | RE | 726ms | 303156kb | C++14 | 755b | 2023-01-14 15:19:31 | 2023-01-14 15:19:33 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=3e4+5,B=880,mod=998244353;
int n,m=800,c,ans;
int f[B][N];
int g[N][B*2];
int main(){
cin>>n>>c;
f[1][m]=1;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(j+m+i<=n) f[i+1][j+m+i]=(f[i+1][j+m+i]+f[i][j])%mod;
if(j+m-i<=n) f[i+1][j+m-i]=(f[i+1][j+m-i]+1ll*f[i][j]*c%mod)%mod;
}
}
for(int t=m;t<=n;t++)
for(int i=1;i<=m && (t-m)*i<=n;i++)
ans=(ans+f[i][n-(t-m)*i])%mod;
for(int t=1;t<m;t++) g[t][t]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=2*m;j++){
if(j>1) g[i+j-1][j-1]=(g[i+j-1][j-1]+1ll*g[i][j]*c%mod)%mod;
if(i+j+1<=n) g[i+j+1][j+1]=(g[i+j+1][j+1]+g[i][j])%mod;
}
}
for(int t=1;t<=2*m;t++) ans=(ans+g[n][t])%mod;
cout<<ans;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 13460kb
input:
5 3
output:
8
result:
ok 1 number(s): "8"
Test #2:
score: 0
Accepted
time: 0ms
memory: 13464kb
input:
1 0
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 40ms
memory: 36664kb
input:
2022 39
output:
273239559
result:
ok 1 number(s): "273239559"
Test #4:
score: 0
Accepted
time: 2ms
memory: 14280kb
input:
1 998244352
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 2ms
memory: 14432kb
input:
1 12345678
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 2ms
memory: 14476kb
input:
20 998998
output:
643731701
result:
ok 1 number(s): "643731701"
Test #7:
score: 0
Accepted
time: 0ms
memory: 14536kb
input:
23 123
output:
947753998
result:
ok 1 number(s): "947753998"
Test #8:
score: 0
Accepted
time: 1ms
memory: 13944kb
input:
50 5555
output:
745339864
result:
ok 1 number(s): "745339864"
Test #9:
score: 0
Accepted
time: 2ms
memory: 14124kb
input:
60 6666
output:
690992218
result:
ok 1 number(s): "690992218"
Test #10:
score: 0
Accepted
time: 3ms
memory: 15380kb
input:
100 50
output:
169678588
result:
ok 1 number(s): "169678588"
Test #11:
score: 0
Accepted
time: 4ms
memory: 20488kb
input:
500 88888
output:
216149701
result:
ok 1 number(s): "216149701"
Test #12:
score: 0
Accepted
time: 24ms
memory: 26652kb
input:
1000 213456
output:
270989457
result:
ok 1 number(s): "270989457"
Test #13:
score: 0
Accepted
time: 32ms
memory: 37044kb
input:
2000 119988
output:
756425375
result:
ok 1 number(s): "756425375"
Test #14:
score: 0
Accepted
time: 69ms
memory: 47192kb
input:
3000 998244352
output:
71841227
result:
ok 1 number(s): "71841227"
Test #15:
score: 0
Accepted
time: 76ms
memory: 46952kb
input:
3000 555555555
output:
79880116
result:
ok 1 number(s): "79880116"
Test #16:
score: 0
Accepted
time: 119ms
memory: 59768kb
input:
4321 1234
output:
949603993
result:
ok 1 number(s): "949603993"
Test #17:
score: 0
Accepted
time: 129ms
memory: 66372kb
input:
5000 0
output:
5
result:
ok 1 number(s): "5"
Test #18:
score: 0
Accepted
time: 94ms
memory: 66832kb
input:
5000 88888777
output:
833064960
result:
ok 1 number(s): "833064960"
Test #19:
score: 0
Accepted
time: 118ms
memory: 66708kb
input:
5000 35557777
output:
696388498
result:
ok 1 number(s): "696388498"
Test #20:
score: 0
Accepted
time: 257ms
memory: 116164kb
input:
10000 123456
output:
434296902
result:
ok 1 number(s): "434296902"
Test #21:
score: 0
Accepted
time: 461ms
memory: 216856kb
input:
20000 555555
output:
34806915
result:
ok 1 number(s): "34806915"
Test #22:
score: 0
Accepted
time: 726ms
memory: 303156kb
input:
30000 777888999
output:
58443551
result:
ok 1 number(s): "58443551"
Test #23:
score: -100
Runtime Error
input:
50000 2