QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #72262 | #4812. Counting Sequence | JinTianHao | WA | 17ms | 22684kb | C++17 | 1.7kb | 2023-01-15 11:40:28 | 2023-01-15 11:40:29 |
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[2][600005];
int dp2[300005][900];
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
read(n);read(c);ans=(n>1&&!c);
siz=sqrt(2*n)-10;siz=max(siz,0);
while((siz+2)*(siz+1)<=2*n) ++siz;
dp1[1][n]=1;
for(int i=1;i<siz;++i)
{
for(int j=0;j<=2*n;++j)
dp1[i&1^1][j]=0;
for(int j=0;j<=2*n;++j)
{
//add <
(dp1[i&1^1][j+i]+=dp1[i&1][j])%=mod;
//add >
(dp1[i&1^1][j-i]+=1ll*c*dp1[i&1][j]%mod)%=mod;
}
for(int a=siz+1;a<=n;++a)
{
int sum=2*n-a*i;
if(sum>=0&&sum<=2*n) (ans+=dp1[i&1][sum])%=mod;
}
}
for(int i=1;i<=n;++i)
{
if(i<=siz) (dp2[i][i]+=1)%=mod;
for(int j=1;j<900;++j)
{
if(!dp2[i][j]) continue;
if(i+j-1<=n&&j>1) (dp2[i+j-1][j-1]+=1ll*c*dp2[i][j]%mod)%=mod;
if(i+j+1<=n&&j<899) (dp2[i+j+1][j+1]+=dp2[i][j])%=mod;
}
}
for(int i=1;i<900;++i)
(ans+=dp2[n][i])%=mod;
for(int a=siz+1;a<=n;++a)
for(int m=siz;m<=siz;++m)
{
int sum=2*n-a*m;
if(sum>=0&&sum<=2*n) (ans+=dp1[m&1][sum])%=mod;
}
writeln(ans);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 7516kb
input:
5 3
output:
8
result:
ok 1 number(s): "8"
Test #2:
score: 0
Accepted
time: 2ms
memory: 5416kb
input:
1 0
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 1ms
memory: 14600kb
input:
2022 39
output:
273239559
result:
ok 1 number(s): "273239559"
Test #4:
score: 0
Accepted
time: 2ms
memory: 5392kb
input:
1 998244352
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 5388kb
input:
1 12345678
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 2ms
memory: 7552kb
input:
20 998998
output:
643731701
result:
ok 1 number(s): "643731701"
Test #7:
score: 0
Accepted
time: 2ms
memory: 7584kb
input:
23 123
output:
947753998
result:
ok 1 number(s): "947753998"
Test #8:
score: 0
Accepted
time: 0ms
memory: 7656kb
input:
50 5555
output:
745339864
result:
ok 1 number(s): "745339864"
Test #9:
score: 0
Accepted
time: 3ms
memory: 7704kb
input:
60 6666
output:
690992218
result:
ok 1 number(s): "690992218"
Test #10:
score: 0
Accepted
time: 0ms
memory: 7836kb
input:
100 50
output:
169678588
result:
ok 1 number(s): "169678588"
Test #11:
score: 0
Accepted
time: 4ms
memory: 9408kb
input:
500 88888
output:
216149701
result:
ok 1 number(s): "216149701"
Test #12:
score: 0
Accepted
time: 1ms
memory: 11024kb
input:
1000 213456
output:
270989457
result:
ok 1 number(s): "270989457"
Test #13:
score: 0
Accepted
time: 4ms
memory: 14536kb
input:
2000 119988
output:
756425375
result:
ok 1 number(s): "756425375"
Test #14:
score: 0
Accepted
time: 4ms
memory: 18036kb
input:
3000 998244352
output:
71841227
result:
ok 1 number(s): "71841227"
Test #15:
score: 0
Accepted
time: 17ms
memory: 18004kb
input:
3000 555555555
output:
79880116
result:
ok 1 number(s): "79880116"
Test #16:
score: 0
Accepted
time: 12ms
memory: 22684kb
input:
4321 1234
output:
949603993
result:
ok 1 number(s): "949603993"
Test #17:
score: -100
Wrong Answer
time: 4ms
memory: 22496kb
input:
5000 0
output:
6
result:
wrong answer 1st numbers differ - expected: '5', found: '6'