QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #72289 | #4812. Counting Sequence | IhpEcVns | ML | 1366ms | 954760kb | C++14 | 641b | 2023-01-15 12:32:13 | 2023-01-15 12:32:16 |
Judging History
answer
//#include<bits/stdc++.h>
//using namespace std;using I=int;enum{N=10000};
//main(){
//}
#include<iostream>
using I=long long;using namespace std;
enum{M=998244353,N=300004};
I n,c,A=1,B,f[N]{1},s[N]{1},g[N][810];
main(){
for(std::cin>>n>>c;B*(B+1)<=n*2;g[B][B]=1)++B;
for(I i=1;i<=B;++i)for(I j=n-B;~j;--j){
I&o=f[j]=B+i<=j?f[j-B-i]:0;
B-i<=j&&(o=(o+f[j-B+i]*c)%M),
j<n-B&&(n-B-j)%(i+1)==0&&(A=(A+o)%M),s[j]=(s[j]+o)%M;
}
for(I i=1;i<=n;++i)for(I j=1;j<=B&&j<i;++j){
I&o=g[i][j]=g[i-j][j-1];
j<B-1&&(o=(o+g[i-j][j+1]*c)%M),
i==n&&j<B&&(A=(A+o)%M),j==B&&(A=(A+o*s[n-i])%M);
}
std::cout<<(A+s[n-B])%M;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3412kb
input:
5 3
output:
8
result:
ok 1 number(s): "8"
Test #2:
score: 0
Accepted
time: 2ms
memory: 3580kb
input:
1 0
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 1ms
memory: 17800kb
input:
2022 39
output:
273239559
result:
ok 1 number(s): "273239559"
Test #4:
score: 0
Accepted
time: 2ms
memory: 3400kb
input:
1 998244352
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 2ms
memory: 3396kb
input:
1 12345678
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
20 998998
output:
643731701
result:
ok 1 number(s): "643731701"
Test #7:
score: 0
Accepted
time: 2ms
memory: 3484kb
input:
23 123
output:
947753998
result:
ok 1 number(s): "947753998"
Test #8:
score: 0
Accepted
time: 1ms
memory: 5848kb
input:
50 5555
output:
745339864
result:
ok 1 number(s): "745339864"
Test #9:
score: 0
Accepted
time: 2ms
memory: 5580kb
input:
60 6666
output:
690992218
result:
ok 1 number(s): "690992218"
Test #10:
score: 0
Accepted
time: 2ms
memory: 5736kb
input:
100 50
output:
169678588
result:
ok 1 number(s): "169678588"
Test #11:
score: 0
Accepted
time: 3ms
memory: 7712kb
input:
500 88888
output:
216149701
result:
ok 1 number(s): "216149701"
Test #12:
score: 0
Accepted
time: 1ms
memory: 10288kb
input:
1000 213456
output:
270989457
result:
ok 1 number(s): "270989457"
Test #13:
score: 0
Accepted
time: 2ms
memory: 16324kb
input:
2000 119988
output:
756425375
result:
ok 1 number(s): "756425375"
Test #14:
score: 0
Accepted
time: 5ms
memory: 23996kb
input:
3000 998244352
output:
71841227
result:
ok 1 number(s): "71841227"
Test #15:
score: 0
Accepted
time: 3ms
memory: 24364kb
input:
3000 555555555
output:
79880116
result:
ok 1 number(s): "79880116"
Test #16:
score: 0
Accepted
time: 4ms
memory: 30872kb
input:
4321 1234
output:
949603993
result:
ok 1 number(s): "949603993"
Test #17:
score: 0
Accepted
time: 7ms
memory: 34888kb
input:
5000 0
output:
5
result:
ok 1 number(s): "5"
Test #18:
score: 0
Accepted
time: 4ms
memory: 35624kb
input:
5000 88888777
output:
833064960
result:
ok 1 number(s): "833064960"
Test #19:
score: 0
Accepted
time: 4ms
memory: 37032kb
input:
5000 35557777
output:
696388498
result:
ok 1 number(s): "696388498"
Test #20:
score: 0
Accepted
time: 16ms
memory: 67100kb
input:
10000 123456
output:
434296902
result:
ok 1 number(s): "434296902"
Test #21:
score: 0
Accepted
time: 58ms
memory: 130044kb
input:
20000 555555
output:
34806915
result:
ok 1 number(s): "34806915"
Test #22:
score: 0
Accepted
time: 120ms
memory: 192960kb
input:
30000 777888999
output:
58443551
result:
ok 1 number(s): "58443551"
Test #23:
score: 0
Accepted
time: 268ms
memory: 320340kb
input:
50000 2
output:
90102905
result:
ok 1 number(s): "90102905"
Test #24:
score: 0
Accepted
time: 437ms
memory: 447284kb
input:
70000 77998866
output:
202638568
result:
ok 1 number(s): "202638568"
Test #25:
score: 0
Accepted
time: 765ms
memory: 637596kb
input:
100000 998244352
output:
360520717
result:
ok 1 number(s): "360520717"
Test #26:
score: 0
Accepted
time: 793ms
memory: 637640kb
input:
100000 555555555
output:
613886009
result:
ok 1 number(s): "613886009"
Test #27:
score: 0
Accepted
time: 1366ms
memory: 954760kb
input:
150000 233333
output:
381065878
result:
ok 1 number(s): "381065878"
Test #28:
score: 0
Accepted
time: 1344ms
memory: 954672kb
input:
150000 20050117
output:
269891864
result:
ok 1 number(s): "269891864"
Test #29:
score: -100
Memory Limit Exceeded
input:
200000 114514