QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#133033 | #4812. Counting Sequence | zyz07 | WA | 5ms | 9708kb | C++17 | 1.1kb | 2023-08-01 13:40:05 | 2023-08-01 13:40:06 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define For(Ti,Ta,Tb) for(auto Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(auto Ti=(Ta);Ti>=(Tb);--Ti)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define range(Tx) begin(Tx),end(Tx)
using ll=long long;
const int N=3e5+5,K3=550*2.2,Mod=998244353;
int n,c,f[K3][K3],g[2][N];
void mod_add(int& x,int y){
x=x+y-(x+y>=Mod?Mod:0);
}
void mod_add(int& x,ll y){
x=(x+y)%Mod;
}
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
cin>>n>>c;
const int k=sqrt(n),k2=1.5*k,k3=2.2*k;
For(i,1,k2-1) f[i][i]=1;
For(j,1,n){
For(i,1,k3-1) f[(j-1)%K3][i]=0;
For(i,1,k3-1) if(f[j%K3][i]){
if(i>1&&j+i-1<=n) mod_add(f[(j+i-1)%K3][i-1],1LL*c*f[j%K3][i]);
if(j+i+1<=n) mod_add(f[(j+i+1)%K3][i+1],f[j%K3][i]);
}
}
ll ans=0;
For(i,1,k3-1) (ans+=f[n%K3][i])%=Mod;
g[1][k2]=1;
For(i,1,k2+1){
For(j,1,n) g[(i&1)^1][j]=0;
For(j,1,n) if(g[i&1][j]){
if(j+k2-i<=n) mod_add(g[(i&1)^1][j+k2-i],1LL*c*g[i&1][j]);
if(j+k2+i<=n) mod_add(g[(i&1)^1][j+k2+i],g[i&1][j]);
}
for(int j=n;j>=1;j-=i) (ans+=g[i&1][j])%=Mod;
}
cout<<ans<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 5692kb
input:
5 3
output:
8
result:
ok 1 number(s): "8"
Test #2:
score: 0
Accepted
time: 2ms
memory: 7524kb
input:
1 0
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 5ms
memory: 9708kb
input:
2022 39
output:
273239559
result:
ok 1 number(s): "273239559"
Test #4:
score: -100
Wrong Answer
time: 2ms
memory: 5524kb
input:
1 998244352
output:
0
result:
wrong answer 1st numbers differ - expected: '1', found: '0'