QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #72145 | #4812. Counting Sequence | Appleblue17 | RE | 797ms | 15724kb | C++14 | 917b | 2023-01-14 15:40:09 | 2023-01-14 15:40:10 |
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[2][N];
int g[B*2][B*2];
bool fl=0;
int nw=1;
int main(){
cin>>n>>c;
fl=0;
f[0][m]=1;
for(int i=1;i<=m;i++){
for(int t=m;t<=n && (t-m)*i<=n;t++)
ans=(ans+f[fl][n-(t-m)*i])%mod;
for(int j=1;j<=n;j++){
if(j+m+i<=n) f[fl^1][j+m+i]=(f[fl^1][j+m+i]+f[fl][j])%mod;
if(j+m-i<=n) f[fl^1][j+m-i]=(f[fl^1][j+m-i]+1ll*f[fl][j]*c%mod)%mod;
}
memset(f[fl],0,sizeof(f[fl]));
fl^=1;
}
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[(nw+j-1)%(2*m)][j-1]=(g[(nw+j-1)%(2*m)][j-1]+1ll*g[nw][j]*c%mod)%mod;
if(i+j+1<=n) g[(nw+j+1)%(2*m)][j+1]=(g[(nw+j+1)%(2*m)][j+1]+g[nw][j])%mod;
}
memset(g[nw],0,sizeof(g[nw]));
nw=(nw+1)%(2*m);
}
for(int t=1;t<=2*m;t++) ans=(ans+g[nw][t])%mod;
cout<<ans;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 11764kb
input:
5 3
output:
8
result:
ok 1 number(s): "8"
Test #2:
score: 0
Accepted
time: 7ms
memory: 9940kb
input:
1 0
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 53ms
memory: 15724kb
input:
2022 39
output:
273239559
result:
ok 1 number(s): "273239559"
Test #4:
score: 0
Accepted
time: 0ms
memory: 8500kb
input:
1 998244352
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 3ms
memory: 8428kb
input:
1 12345678
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 5ms
memory: 11764kb
input:
20 998998
output:
643731701
result:
ok 1 number(s): "643731701"
Test #7:
score: 0
Accepted
time: 5ms
memory: 12660kb
input:
23 123
output:
947753998
result:
ok 1 number(s): "947753998"
Test #8:
score: 0
Accepted
time: 3ms
memory: 12712kb
input:
50 5555
output:
745339864
result:
ok 1 number(s): "745339864"
Test #9:
score: 0
Accepted
time: 5ms
memory: 12052kb
input:
60 6666
output:
690992218
result:
ok 1 number(s): "690992218"
Test #10:
score: 0
Accepted
time: 8ms
memory: 12308kb
input:
100 50
output:
169678588
result:
ok 1 number(s): "169678588"
Test #11:
score: 0
Accepted
time: 13ms
memory: 13904kb
input:
500 88888
output:
216149701
result:
ok 1 number(s): "216149701"
Test #12:
score: 0
Accepted
time: 32ms
memory: 14524kb
input:
1000 213456
output:
270989457
result:
ok 1 number(s): "270989457"
Test #13:
score: 0
Accepted
time: 53ms
memory: 14524kb
input:
2000 119988
output:
756425375
result:
ok 1 number(s): "756425375"
Test #14:
score: 0
Accepted
time: 85ms
memory: 14568kb
input:
3000 998244352
output:
71841227
result:
ok 1 number(s): "71841227"
Test #15:
score: 0
Accepted
time: 85ms
memory: 14532kb
input:
3000 555555555
output:
79880116
result:
ok 1 number(s): "79880116"
Test #16:
score: 0
Accepted
time: 109ms
memory: 14532kb
input:
4321 1234
output:
949603993
result:
ok 1 number(s): "949603993"
Test #17:
score: 0
Accepted
time: 123ms
memory: 14420kb
input:
5000 0
output:
5
result:
ok 1 number(s): "5"
Test #18:
score: 0
Accepted
time: 121ms
memory: 14560kb
input:
5000 88888777
output:
833064960
result:
ok 1 number(s): "833064960"
Test #19:
score: 0
Accepted
time: 123ms
memory: 14676kb
input:
5000 35557777
output:
696388498
result:
ok 1 number(s): "696388498"
Test #20:
score: 0
Accepted
time: 247ms
memory: 14556kb
input:
10000 123456
output:
434296902
result:
ok 1 number(s): "434296902"
Test #21:
score: 0
Accepted
time: 509ms
memory: 14564kb
input:
20000 555555
output:
34806915
result:
ok 1 number(s): "34806915"
Test #22:
score: 0
Accepted
time: 797ms
memory: 14508kb
input:
30000 777888999
output:
58443551
result:
ok 1 number(s): "58443551"
Test #23:
score: -100
Runtime Error
input:
50000 2