QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #72169 | #4812. Counting Sequence | zhangboju | RE | 1453ms | 7496kb | C++14 | 1011b | 2023-01-14 19:03:01 | 2023-01-14 19:03:03 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &x)
{
x=0;short f=1;char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x*=f;return;
}
const int N=3e5+5,B=650,mod=998244353;
int n,c,f[N],g[N],h[B+10][B+10],ans;
int main()
{
read(n),read(c);
ans=(n>B);
for(int i=f[0]=g[0]=1,j,flg=1;flg;++i)
{
for(j=n-B,flg=0;j>=0;--j)
{
f[j]=((B+i<=j)?f[j-B-i]:0);
if(B-i<=j) f[j]=(f[j]+f[j-B+i]*1ll*c)%mod;
if(j<n-B&&(n-B-j)%(i+1)==0)
ans=(ans+f[j])%mod;
g[j]=(g[j]+f[j])%mod;
flg|=!!f[j];
}
}
for(int i=1;i<=B;++i)
h[i][i]=1;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=B&&j<i;++j)
{
h[i%(B+1)][j]=h[(i-j)%(B+1)][j-1];
if(j+1<B) h[i%(B+1)][j]=(h[i%(B+1)][j]+h[(i-j)%(B+1)][j+1]*1ll*c)%mod;
}
ans=(ans+h[i%(B+1)][B]*1ll*g[n-i])%mod;
}
for(int i=1;i<B;++i)
ans=(ans+h[n%(B+1)][i])%mod;
printf("%d\n",ans);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 5116kb
input:
5 3
output:
8
result:
ok 1 number(s): "8"
Test #2:
score: 0
Accepted
time: 3ms
memory: 5048kb
input:
1 0
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 8ms
memory: 5296kb
input:
2022 39
output:
273239559
result:
ok 1 number(s): "273239559"
Test #4:
score: 0
Accepted
time: 1ms
memory: 5116kb
input:
1 998244352
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 3ms
memory: 5112kb
input:
1 12345678
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 1ms
memory: 5140kb
input:
20 998998
output:
643731701
result:
ok 1 number(s): "643731701"
Test #7:
score: 0
Accepted
time: 0ms
memory: 5152kb
input:
23 123
output:
947753998
result:
ok 1 number(s): "947753998"
Test #8:
score: 0
Accepted
time: 3ms
memory: 5072kb
input:
50 5555
output:
745339864
result:
ok 1 number(s): "745339864"
Test #9:
score: 0
Accepted
time: 0ms
memory: 5156kb
input:
60 6666
output:
690992218
result:
ok 1 number(s): "690992218"
Test #10:
score: 0
Accepted
time: 1ms
memory: 5180kb
input:
100 50
output:
169678588
result:
ok 1 number(s): "169678588"
Test #11:
score: 0
Accepted
time: 1ms
memory: 5104kb
input:
500 88888
output:
216149701
result:
ok 1 number(s): "216149701"
Test #12:
score: 0
Accepted
time: 5ms
memory: 5180kb
input:
1000 213456
output:
270989457
result:
ok 1 number(s): "270989457"
Test #13:
score: 0
Accepted
time: 4ms
memory: 5296kb
input:
2000 119988
output:
756425375
result:
ok 1 number(s): "756425375"
Test #14:
score: 0
Accepted
time: 11ms
memory: 5136kb
input:
3000 998244352
output:
71841227
result:
ok 1 number(s): "71841227"
Test #15:
score: 0
Accepted
time: 11ms
memory: 5060kb
input:
3000 555555555
output:
79880116
result:
ok 1 number(s): "79880116"
Test #16:
score: 0
Accepted
time: 11ms
memory: 5340kb
input:
4321 1234
output:
949603993
result:
ok 1 number(s): "949603993"
Test #17:
score: 0
Accepted
time: 17ms
memory: 5176kb
input:
5000 0
output:
5
result:
ok 1 number(s): "5"
Test #18:
score: 0
Accepted
time: 17ms
memory: 5148kb
input:
5000 88888777
output:
833064960
result:
ok 1 number(s): "833064960"
Test #19:
score: 0
Accepted
time: 17ms
memory: 5352kb
input:
5000 35557777
output:
696388498
result:
ok 1 number(s): "696388498"
Test #20:
score: 0
Accepted
time: 34ms
memory: 5212kb
input:
10000 123456
output:
434296902
result:
ok 1 number(s): "434296902"
Test #21:
score: 0
Accepted
time: 67ms
memory: 5440kb
input:
20000 555555
output:
34806915
result:
ok 1 number(s): "34806915"
Test #22:
score: 0
Accepted
time: 102ms
memory: 5556kb
input:
30000 777888999
output:
58443551
result:
ok 1 number(s): "58443551"
Test #23:
score: 0
Accepted
time: 176ms
memory: 5556kb
input:
50000 2
output:
90102905
result:
ok 1 number(s): "90102905"
Test #24:
score: 0
Accepted
time: 261ms
memory: 5724kb
input:
70000 77998866
output:
202638568
result:
ok 1 number(s): "202638568"
Test #25:
score: 0
Accepted
time: 393ms
memory: 5892kb
input:
100000 998244352
output:
360520717
result:
ok 1 number(s): "360520717"
Test #26:
score: 0
Accepted
time: 390ms
memory: 5760kb
input:
100000 555555555
output:
613886009
result:
ok 1 number(s): "613886009"
Test #27:
score: 0
Accepted
time: 672ms
memory: 6348kb
input:
150000 233333
output:
381065878
result:
ok 1 number(s): "381065878"
Test #28:
score: 0
Accepted
time: 658ms
memory: 6548kb
input:
150000 20050117
output:
269891864
result:
ok 1 number(s): "269891864"
Test #29:
score: 0
Accepted
time: 1057ms
memory: 6604kb
input:
200000 114514
output:
262861613
result:
ok 1 number(s): "262861613"
Test #30:
score: 0
Accepted
time: 1087ms
memory: 6884kb
input:
200000 1919810
output:
77872388
result:
ok 1 number(s): "77872388"
Test #31:
score: 0
Accepted
time: 1453ms
memory: 7496kb
input:
300000 0
output:
12
result:
ok 1 number(s): "12"
Test #32:
score: -100
Runtime Error
input:
300000 1