QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#133033#4812. Counting Sequencezyz07WA 5ms9708kbC++171.1kb2023-08-01 13:40:052023-08-01 13:40:06

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-01 13:40:06]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:9708kb
  • [2023-08-01 13:40:05]
  • 提交

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'