QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#72279 | #4812. Counting Sequence | JinTianHao | AC ✓ | 2543ms | 949280kb | C++17 | 1.4kb | 2023-01-15 11:55:36 | 2023-01-15 11:55:40 |
Judging History
answer
#include <bits/stdc++.h>
#define inf 1000000007
#define mod 998244353
// #define int long long
// #pragma GCC optimize("Ofast","inline","-ffast-math")
// #pragma GCC target("avx,sse2,sse3,sse4,mmx")
using namespace std;
template <typename T> void read(T &x){
x=0;char ch=getchar();int fh=1;
while (ch<'0'||ch>'9'){if (ch=='-')fh=-1;ch=getchar();}
while (ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
x*=fh;
}
template <typename T> void write(T x) {
if (x<0) x=-x,putchar('-');
if (x>9) write(x/10);
putchar(x%10+'0');
}
template <typename T> void writeln(T x) {
write(x);
puts("");
}
int n,c,siz,ans;
int dp1[300005],z[300005];
int dp2[300005][805];
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
read(n);read(c);dp1[0]=z[0]=1;ans=n>1;
while(siz*(siz+1)<=2*n) ++siz;
for(int i=1;i<=siz;++i)
for(int j=n-siz;j>=0;--j)
{
dp1[j]=0;
if(siz+i<=j) dp1[j]=dp1[j-siz-i];
if(siz-i<=j) (dp1[j]+=1ll*dp1[j-siz+i]*c%mod)%=mod;
if(j<n-siz&&(n-siz-j)%(i+1)==0) (ans+=dp1[j])%=mod;
(z[j]+=dp1[j])%=mod;
}
for(int i=1;i<=siz;++i)
dp2[i][i]=1;
for(int i=1;i<=n;++i)
for(int j=1;j<=siz&&j<i;++j)
{
dp2[i][j]=dp2[i-j][j-1];
if(j<siz-1) (dp2[i][j]+=1ll*dp2[i-j][j+1]*c%mod)%=mod;
}
for(int i=1;i<siz;++i) (ans+=dp2[n][i])%=mod;
for(int i=1;i<=n;++i) (ans+=1ll*dp2[i][siz]*z[n-i]%mod)%=mod;
writeln(ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 5392kb
input:
5 3
output:
8
result:
ok 1 number(s): "8"
Test #2:
score: 0
Accepted
time: 2ms
memory: 5388kb
input:
1 0
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 6ms
memory: 15176kb
input:
2022 39
output:
273239559
result:
ok 1 number(s): "273239559"
Test #4:
score: 0
Accepted
time: 2ms
memory: 5448kb
input:
1 998244352
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 5624kb
input:
1 12345678
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 0ms
memory: 5484kb
input:
20 998998
output:
643731701
result:
ok 1 number(s): "643731701"
Test #7:
score: 0
Accepted
time: 2ms
memory: 5536kb
input:
23 123
output:
947753998
result:
ok 1 number(s): "947753998"
Test #8:
score: 0
Accepted
time: 1ms
memory: 7772kb
input:
50 5555
output:
745339864
result:
ok 1 number(s): "745339864"
Test #9:
score: 0
Accepted
time: 1ms
memory: 5576kb
input:
60 6666
output:
690992218
result:
ok 1 number(s): "690992218"
Test #10:
score: 0
Accepted
time: 2ms
memory: 5700kb
input:
100 50
output:
169678588
result:
ok 1 number(s): "169678588"
Test #11:
score: 0
Accepted
time: 3ms
memory: 7896kb
input:
500 88888
output:
216149701
result:
ok 1 number(s): "216149701"
Test #12:
score: 0
Accepted
time: 4ms
memory: 10496kb
input:
1000 213456
output:
270989457
result:
ok 1 number(s): "270989457"
Test #13:
score: 0
Accepted
time: 2ms
memory: 12080kb
input:
2000 119988
output:
756425375
result:
ok 1 number(s): "756425375"
Test #14:
score: 0
Accepted
time: 10ms
memory: 17024kb
input:
3000 998244352
output:
71841227
result:
ok 1 number(s): "71841227"
Test #15:
score: 0
Accepted
time: 4ms
memory: 17252kb
input:
3000 555555555
output:
79880116
result:
ok 1 number(s): "79880116"
Test #16:
score: 0
Accepted
time: 5ms
memory: 20316kb
input:
4321 1234
output:
949603993
result:
ok 1 number(s): "949603993"
Test #17:
score: 0
Accepted
time: 7ms
memory: 23280kb
input:
5000 0
output:
5
result:
ok 1 number(s): "5"
Test #18:
score: 0
Accepted
time: 3ms
memory: 22920kb
input:
5000 88888777
output:
833064960
result:
ok 1 number(s): "833064960"
Test #19:
score: 0
Accepted
time: 3ms
memory: 23268kb
input:
5000 35557777
output:
696388498
result:
ok 1 number(s): "696388498"
Test #20:
score: 0
Accepted
time: 8ms
memory: 39580kb
input:
10000 123456
output:
434296902
result:
ok 1 number(s): "434296902"
Test #21:
score: 0
Accepted
time: 38ms
memory: 69568kb
input:
20000 555555
output:
34806915
result:
ok 1 number(s): "34806915"
Test #22:
score: 0
Accepted
time: 74ms
memory: 103024kb
input:
30000 777888999
output:
58443551
result:
ok 1 number(s): "58443551"
Test #23:
score: 0
Accepted
time: 156ms
memory: 166780kb
input:
50000 2
output:
90102905
result:
ok 1 number(s): "90102905"
Test #24:
score: 0
Accepted
time: 253ms
memory: 227140kb
input:
70000 77998866
output:
202638568
result:
ok 1 number(s): "202638568"
Test #25:
score: 0
Accepted
time: 445ms
memory: 320988kb
input:
100000 998244352
output:
360520717
result:
ok 1 number(s): "360520717"
Test #26:
score: 0
Accepted
time: 445ms
memory: 321760kb
input:
100000 555555555
output:
613886009
result:
ok 1 number(s): "613886009"
Test #27:
score: 0
Accepted
time: 926ms
memory: 477772kb
input:
150000 233333
output:
381065878
result:
ok 1 number(s): "381065878"
Test #28:
score: 0
Accepted
time: 913ms
memory: 477752kb
input:
150000 20050117
output:
269891864
result:
ok 1 number(s): "269891864"
Test #29:
score: 0
Accepted
time: 1340ms
memory: 634784kb
input:
200000 114514
output:
262861613
result:
ok 1 number(s): "262861613"
Test #30:
score: 0
Accepted
time: 1338ms
memory: 634320kb
input:
200000 1919810
output:
77872388
result:
ok 1 number(s): "77872388"
Test #31:
score: 0
Accepted
time: 2542ms
memory: 949164kb
input:
300000 0
output:
12
result:
ok 1 number(s): "12"
Test #32:
score: 0
Accepted
time: 2443ms
memory: 949028kb
input:
300000 1
output:
298803948
result:
ok 1 number(s): "298803948"
Test #33:
score: 0
Accepted
time: 2512ms
memory: 949236kb
input:
300000 2
output:
106751203
result:
ok 1 number(s): "106751203"
Test #34:
score: 0
Accepted
time: 2512ms
memory: 949280kb
input:
300000 1234
output:
427045479
result:
ok 1 number(s): "427045479"
Test #35:
score: 0
Accepted
time: 2521ms
memory: 949048kb
input:
300000 2345
output:
441593553
result:
ok 1 number(s): "441593553"
Test #36:
score: 0
Accepted
time: 2443ms
memory: 949168kb
input:
300000 20041115
output:
580367993
result:
ok 1 number(s): "580367993"
Test #37:
score: 0
Accepted
time: 2508ms
memory: 949256kb
input:
300000 20050117
output:
579859619
result:
ok 1 number(s): "579859619"
Test #38:
score: 0
Accepted
time: 2543ms
memory: 949048kb
input:
300000 22223333
output:
596066085
result:
ok 1 number(s): "596066085"
Test #39:
score: 0
Accepted
time: 2468ms
memory: 949164kb
input:
300000 175846372
output:
660364393
result:
ok 1 number(s): "660364393"
Test #40:
score: 0
Accepted
time: 2427ms
memory: 949052kb
input:
299999 9999999
output:
954865020
result:
ok 1 number(s): "954865020"
Test #41:
score: 0
Accepted
time: 2531ms
memory: 949164kb
input:
299998 55556666
output:
904862432
result:
ok 1 number(s): "904862432"
Test #42:
score: 0
Accepted
time: 1214ms
memory: 606264kb
input:
190733 31756136
output:
880544587
result:
ok 1 number(s): "880544587"
Test #43:
score: 0
Accepted
time: 1345ms
memory: 630524kb
input:
198497 463488298
output:
185220207
result:
ok 1 number(s): "185220207"
Test #44:
score: 0
Accepted
time: 2473ms
memory: 948976kb
input:
299997 0
output:
16
result:
ok 1 number(s): "16"
Test #45:
score: 0
Accepted
time: 987ms
memory: 534964kb
input:
168168 296157813
output:
798716760
result:
ok 1 number(s): "798716760"
Test #46:
score: 0
Accepted
time: 555ms
memory: 366748kb
input:
114514 1919810
output:
783513290
result:
ok 1 number(s): "783513290"