QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#56346#1423. BintricyzhkxAC ✓2619ms23964kbC++141.9kb2022-10-18 21:10:152022-10-18 21:10:16

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-18 21:10:16]
  • 评测
  • 测评结果:AC
  • 用时:2619ms
  • 内存:23964kb
  • [2022-10-18 21:10:15]
  • 提交

answer

# include <bits/stdc++.h>
using namespace std;
const int mod=998244353,g=3,_2=(mod+1)/2;
typedef long long ll;
int K,f[1000010],F[2100000],G[2100000],rev[2100000],w[2100000],maxn;
int add(int a,int b){return (a+=b)>=mod?a-mod:a;}
ll power(ll a,int b)
{
	ll ans=1;
	for(;b;b>>=1,a=a*a%mod)
		if(b&1) ans=ans*a%mod;
	return ans;
}
void init(int len)
{
	int l=0;maxn=1;
	while(maxn<=len) maxn<<=1,l++;
	for(int i=0;i<maxn;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
	for(int i=1;i<maxn;i<<=1)
	{
		ll wm=power(g,(mod-1)/(i<<1));w[i]=1;
		for(int j=1;j<i;j++) w[i+j]=w[i+j-1]*wm%mod;
	}
}
void NTT(int *a,bool flag)
{
	for(int i=0;i<maxn;i++)
		if(i<rev[i]) swap(a[i],a[rev[i]]);
	for(int i=1;i<maxn;i<<=1)
		for(int j=0;j<maxn;j+=i<<1)
			for(int k=j;k<j+i;k++)
			{
				int x=a[k],y=(ll)w[i+k-j]*a[k+i]%mod;
				a[k]=add(x,y);a[k+i]=add(x,mod-y);
			}
	if(!flag)
	{
		int inv=power(maxn,mod-2);
		reverse(a+1,a+maxn);
		for(int i=0;i<maxn;i++) a[i]=(ll)a[i]*inv%mod;
	}
}
void solve(int l,int r)
{
	if(l==r)
	{
		if(l<=1) return;
		if(!(l&1)) f[l]=(f[l]+(ll)f[l/2]*f[l/2])%mod;
		f[l]=(ll)_2*f[l]%mod;
		for(int i=l/2+1;i<=min((l+K)/2,l-1);i++) f[l]=(f[l]+(ll)f[i]*f[l-i])%mod;
		return;
	}
	int mid=(l+r)/2;
	solve(l,mid);
	if(!l)
	{
		for(int i=0;i<=mid;i++) F[i]=f[i];
		init(mid<<1);
		NTT(F,1);
		for(int i=0;i<maxn;i++) F[i]=(ll)F[i]*F[i]%mod;
		NTT(F,0);
		for(int i=mid+1;i<=r;i++) f[i]=add(f[i],F[i]);
		for(int i=0;i<maxn;i++) F[i]=0;
	}
	else
	{
		for(int i=l;i<=mid;i++) F[i-l]=f[i];
		for(int i=0;i<=r-l;i++) G[i]=f[i];
		init(mid-l+r-l);
		NTT(F,1);NTT(G,1);
		for(int i=0;i<maxn;i++) F[i]=(ll)F[i]*G[i]%mod;
		NTT(F,0);
		for(int i=mid+1;i<=r;i++) f[i]=(f[i]+2ll*F[i-l])%mod;
		for(int i=0;i<maxn;i++) F[i]=G[i]=0;
	}
	solve(mid+1,r);
}
int main()
{
	int n;f[1]=1;
	cin>>n>>K;
	solve(0,n);
	cout<<f[n]<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 3600kb

input:

2 0

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3468kb

input:

3 0

output:

1

result:

ok 1 number(s): "1"

Test #3:

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

input:

3 1

output:

2

result:

ok 1 number(s): "2"

Test #4:

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

input:

4 0

output:

2

result:

ok 1 number(s): "2"

Test #5:

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

input:

4 1

output:

3

result:

ok 1 number(s): "3"

Test #6:

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

input:

4 2

output:

5

result:

ok 1 number(s): "5"

Test #7:

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

input:

6 2

output:

23

result:

ok 1 number(s): "23"

Test #8:

score: 0
Accepted
time: 1ms
memory: 3608kb

input:

7 42

output:

132

result:

ok 1 number(s): "132"

Test #9:

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

input:

10 1

output:

400

result:

ok 1 number(s): "400"

Test #10:

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

input:

13 4

output:

42003

result:

ok 1 number(s): "42003"

Test #11:

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

input:

239 17

output:

385818773

result:

ok 1 number(s): "385818773"

Test #12:

score: 0
Accepted
time: 108ms
memory: 4788kb

input:

50216 58

output:

744498776

result:

ok 1 number(s): "744498776"

Test #13:

score: 0
Accepted
time: 2440ms
memory: 23044kb

input:

787788 78

output:

394429402

result:

ok 1 number(s): "394429402"

Test #14:

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

input:

5 92

output:

14

result:

ok 1 number(s): "14"

Test #15:

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

input:

88 79

output:

931161641

result:

ok 1 number(s): "931161641"

Test #16:

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

input:

749 77

output:

615055472

result:

ok 1 number(s): "615055472"

Test #17:

score: 0
Accepted
time: 5ms
memory: 3772kb

input:

2281 89

output:

282226588

result:

ok 1 number(s): "282226588"

Test #18:

score: 0
Accepted
time: 11ms
memory: 3852kb

input:

5765 35

output:

293680396

result:

ok 1 number(s): "293680396"

Test #19:

score: 0
Accepted
time: 53ms
memory: 4768kb

input:

43189 12

output:

805295564

result:

ok 1 number(s): "805295564"

Test #20:

score: 0
Accepted
time: 2371ms
memory: 23008kb

input:

806855 5

output:

593114139

result:

ok 1 number(s): "593114139"

Test #21:

score: 0
Accepted
time: 2551ms
memory: 23736kb

input:

994514 45

output:

678426421

result:

ok 1 number(s): "678426421"

Test #22:

score: 0
Accepted
time: 2558ms
memory: 23812kb

input:

999921 62

output:

752162081

result:

ok 1 number(s): "752162081"

Test #23:

score: 0
Accepted
time: 2606ms
memory: 23744kb

input:

995033 94

output:

130314865

result:

ok 1 number(s): "130314865"

Test #24:

score: 0
Accepted
time: 2541ms
memory: 23656kb

input:

901438 97

output:

809128292

result:

ok 1 number(s): "809128292"

Test #25:

score: 0
Accepted
time: 2485ms
memory: 23800kb

input:

993020 0

output:

926771801

result:

ok 1 number(s): "926771801"

Test #26:

score: 0
Accepted
time: 2619ms
memory: 23964kb

input:

1000000 100

output:

470305140

result:

ok 1 number(s): "470305140"