QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#831759#1423. BinhxhhxhAC ✓3123ms53620kbC++231.3kb2024-12-25 16:41:162024-12-25 16:41:20

Judging History

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

  • [2024-12-25 16:41:20]
  • 评测
  • 测评结果:AC
  • 用时:3123ms
  • 内存:53620kb
  • [2024-12-25 16:41:16]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define mod 998244353
using namespace std;
int n,k,f[1000006],a[4100006],b[4100006],c[4100006],r[4100006];
int pw(int x,int p){
	int res=1;
	for(;p;p>>=1,x=x*x%mod) if(p&1) res=res*x%mod;
	return res;
}
void NTT(int*A,int N,int t=1){
	for(int i=0,k=__lg(N)-1;i<N;i++) r[i]=(r[i>>1]>>1)|((i&1)<<k);
	for(int i=0;i<N;i++) if(i<r[i]) swap(A[i],A[r[i]]);
	int nw=(mod-1)/2;
	for(int i=1;i<N;i+=i){
		int Wn=pw(pw(114514,t),nw);
		for(int j=0;j<N;j+=i+i){
			int w=1;
			for(int k=0;k<i;k++){
				int x=A[j+k],y=w*A[j+k+i]%mod;
				A[j+k]=(x+y)%mod;
				A[j+k+i]=(x-y+mod)%mod;
				w=w*Wn%mod;
			}
		}
		nw/=2;
	}
	if(t>1) for(int i=0,w=pw(N,mod-2);i<N;i++) A[i]=A[i]*w%mod;
}
void slv(int l,int r){
	if(l==r){
		if(l%2==1) f[l]=(f[l]+f[l/2]*f[l/2])%mod;
		f[l]=f[l]*(mod+1)/2%mod;
		for(int i=(l+1)/2;i-(l-i-1)<=k&&i<l;i++) f[l]=(f[l]+f[i]*f[l-i-1])%mod;
		return;
	}
	int mid=l+r>>1;
	slv(l,mid);
	int N=r-l+1;
	while((N&-N)<N) N+=N&-N;
	for(int i=0;i<N;i++) b[i]=i<=mid?f[i]:0;
	for(int i=0;i<N;i++) a[i]=i+l<=mid?f[i+l]:0;
	NTT(a,N);
	NTT(b,N);
	for(int i=0;i<N;i++) c[i]=a[i]*b[i]%mod;
	NTT(c,N,mod-2);
	for(int i=mid+1;i<=r;i++) f[i]=(f[i]+c[i-1-l]*(1+!!l))%mod;
	slv(mid+1,r);
}
signed main(){
	cin>>n>>k;
	f[0]=2;
	slv(0,n-1);
	cout<<f[n-1];
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 11820kb

input:

2 0

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 0ms
memory: 11884kb

input:

3 0

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 2ms
memory: 11752kb

input:

3 1

output:

2

result:

ok 1 number(s): "2"

Test #4:

score: 0
Accepted
time: 2ms
memory: 11880kb

input:

4 0

output:

2

result:

ok 1 number(s): "2"

Test #5:

score: 0
Accepted
time: 0ms
memory: 11880kb

input:

4 1

output:

3

result:

ok 1 number(s): "3"

Test #6:

score: 0
Accepted
time: 0ms
memory: 11700kb

input:

4 2

output:

5

result:

ok 1 number(s): "5"

Test #7:

score: 0
Accepted
time: 0ms
memory: 11896kb

input:

6 2

output:

23

result:

ok 1 number(s): "23"

Test #8:

score: 0
Accepted
time: 2ms
memory: 11880kb

input:

7 42

output:

132

result:

ok 1 number(s): "132"

Test #9:

score: 0
Accepted
time: 0ms
memory: 11820kb

input:

10 1

output:

400

result:

ok 1 number(s): "400"

Test #10:

score: 0
Accepted
time: 2ms
memory: 11696kb

input:

13 4

output:

42003

result:

ok 1 number(s): "42003"

Test #11:

score: 0
Accepted
time: 0ms
memory: 11820kb

input:

239 17

output:

385818773

result:

ok 1 number(s): "385818773"

Test #12:

score: 0
Accepted
time: 133ms
memory: 14436kb

input:

50216 58

output:

744498776

result:

ok 1 number(s): "744498776"

Test #13:

score: 0
Accepted
time: 2938ms
memory: 51900kb

input:

787788 78

output:

394429402

result:

ok 1 number(s): "394429402"

Test #14:

score: 0
Accepted
time: 2ms
memory: 11820kb

input:

5 92

output:

14

result:

ok 1 number(s): "14"

Test #15:

score: 0
Accepted
time: 0ms
memory: 11696kb

input:

88 79

output:

931161641

result:

ok 1 number(s): "931161641"

Test #16:

score: 0
Accepted
time: 3ms
memory: 11760kb

input:

749 77

output:

615055472

result:

ok 1 number(s): "615055472"

Test #17:

score: 0
Accepted
time: 2ms
memory: 13860kb

input:

2281 89

output:

282226588

result:

ok 1 number(s): "282226588"

Test #18:

score: 0
Accepted
time: 15ms
memory: 11892kb

input:

5765 35

output:

293680396

result:

ok 1 number(s): "293680396"

Test #19:

score: 0
Accepted
time: 126ms
memory: 12252kb

input:

43189 12

output:

805295564

result:

ok 1 number(s): "805295564"

Test #20:

score: 0
Accepted
time: 2856ms
memory: 52036kb

input:

806855 5

output:

593114139

result:

ok 1 number(s): "593114139"

Test #21:

score: 0
Accepted
time: 3020ms
memory: 51456kb

input:

994514 45

output:

678426421

result:

ok 1 number(s): "678426421"

Test #22:

score: 0
Accepted
time: 3034ms
memory: 53620kb

input:

999921 62

output:

752162081

result:

ok 1 number(s): "752162081"

Test #23:

score: 0
Accepted
time: 3112ms
memory: 51536kb

input:

995033 94

output:

130314865

result:

ok 1 number(s): "130314865"

Test #24:

score: 0
Accepted
time: 3035ms
memory: 52660kb

input:

901438 97

output:

809128292

result:

ok 1 number(s): "809128292"

Test #25:

score: 0
Accepted
time: 2957ms
memory: 53372kb

input:

993020 0

output:

926771801

result:

ok 1 number(s): "926771801"

Test #26:

score: 0
Accepted
time: 3123ms
memory: 51436kb

input:

1000000 100

output:

470305140

result:

ok 1 number(s): "470305140"