QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#66064#1423. BineyiigjknAC ✓2130ms31908kbC++142.2kb2022-12-06 10:08:282022-12-06 10:08:28

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-06 10:08:28]
  • 评测
  • 测评结果:AC
  • 用时:2130ms
  • 内存:31908kb
  • [2022-12-06 10:08:28]
  • 提交

answer

# include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
constexpr int mod=998244353,g=3,_2=499122177;
int K,maxn,rev[2100000],pwg[2100000],f[1000010],F[2100000],G[2100000];
inline int add(int x,int y){return (x+=y)<mod?x:x-mod;}
inline void upd(int &x,const int &y){if((x+=y)>=mod) x-=mod;}
inline void upd(int &x,const ll &y){x=(x+y)%mod;}
int power(int a,int b)
{
	int ans=1;
	for(;b;b>>=1,a=(ll)a*a%mod)
		if(b&1) ans=(ll)ans*a%mod;
	return ans;
}
void init(int n)
{
	int l=0;
	for(maxn=1;maxn<n;maxn<<=1) l++;
	for(int i=1;i<maxn;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<l-1);
	for(int i=1;i<maxn;i<<=1)
	{
		int wm=power(g,(mod-1)/(i<<1));
		pwg[i]=1;
		for(int j=1;j<i;j++) pwg[i+j]=(ll)pwg[i+j-1]*wm%mod;
	}
}
void NTT(int *p,bool flag)
{
	static ull a[2100000];
	for(int i=0;i<maxn;i++) a[i]=p[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++)
			{
				ull x=a[k],y=a[k+i]*pwg[i-j+k]%mod;
				a[k]=x+y;a[k+i]=x-y+mod;
			}
		if(i==1024) for(int j=0;j<maxn;j++) a[j]%=mod;
	}
	for(int i=0;i<maxn;i++) p[i]=a[i]%mod;
	if(flag) return;
	int invn=power(maxn,mod-2);
	reverse(p+1,p+maxn);
	for(int i=0;i<maxn;i++) p[i]=(ll)p[i]*invn%mod;
}
void slv(int l,int r)
{
	if(l==r)
	{
		if(l==0) return f[l]=0,void();
		else if(l==1) return f[l]=1,void();
		if(~l&1) upd(f[l],(ll)f[l/2]*f[l/2]);
		f[l]=(ll)f[l]*_2%mod;
		for(int i=l/2+1;i<l && i-(l-i)<=K;i++) upd(f[l],(ll)f[i]*f[l-i]);
		return;
	}
	int mid=(l+r)/2;
	slv(l,mid);
	if(l)
	{
		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+1);
		NTT(F,1);NTT(G,1);
		for(int i=0;i<maxn;i++) F[i]=2ll*F[i]*G[i]%mod;
		NTT(F,0);
		for(int i=mid+1;i<=r;i++) upd(f[i],F[i-l]);
		memset(F,0,sizeof(int)*maxn);
		memset(G,0,sizeof(int)*maxn);
	}
	else
	{
		for(int i=l;i<=mid;i++) F[i]=f[i];
		init(2*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++) upd(f[i],F[i]);
		memset(F,0,sizeof(int)*maxn);
	}
	slv(mid+1,r);
}
int main()
{
	int n;
	cin>>n>>K;
	slv(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: 2ms
memory: 3400kb

input:

2 0

output:

1

result:

ok 1 number(s): "1"

Test #2:

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

input:

3 0

output:

1

result:

ok 1 number(s): "1"

Test #3:

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

input:

3 1

output:

2

result:

ok 1 number(s): "2"

Test #4:

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

input:

4 0

output:

2

result:

ok 1 number(s): "2"

Test #5:

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

input:

4 1

output:

3

result:

ok 1 number(s): "3"

Test #6:

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

input:

4 2

output:

5

result:

ok 1 number(s): "5"

Test #7:

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

input:

6 2

output:

23

result:

ok 1 number(s): "23"

Test #8:

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

input:

7 42

output:

132

result:

ok 1 number(s): "132"

Test #9:

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

input:

10 1

output:

400

result:

ok 1 number(s): "400"

Test #10:

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

input:

13 4

output:

42003

result:

ok 1 number(s): "42003"

Test #11:

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

input:

239 17

output:

385818773

result:

ok 1 number(s): "385818773"

Test #12:

score: 0
Accepted
time: 88ms
memory: 5064kb

input:

50216 58

output:

744498776

result:

ok 1 number(s): "744498776"

Test #13:

score: 0
Accepted
time: 1920ms
memory: 30948kb

input:

787788 78

output:

394429402

result:

ok 1 number(s): "394429402"

Test #14:

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

input:

5 92

output:

14

result:

ok 1 number(s): "14"

Test #15:

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

input:

88 79

output:

931161641

result:

ok 1 number(s): "931161641"

Test #16:

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

input:

749 77

output:

615055472

result:

ok 1 number(s): "615055472"

Test #17:

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

input:

2281 89

output:

282226588

result:

ok 1 number(s): "282226588"

Test #18:

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

input:

5765 35

output:

293680396

result:

ok 1 number(s): "293680396"

Test #19:

score: 0
Accepted
time: 46ms
memory: 4944kb

input:

43189 12

output:

805295564

result:

ok 1 number(s): "805295564"

Test #20:

score: 0
Accepted
time: 1832ms
memory: 30960kb

input:

806855 5

output:

593114139

result:

ok 1 number(s): "593114139"

Test #21:

score: 0
Accepted
time: 2070ms
memory: 31832kb

input:

994514 45

output:

678426421

result:

ok 1 number(s): "678426421"

Test #22:

score: 0
Accepted
time: 2076ms
memory: 31824kb

input:

999921 62

output:

752162081

result:

ok 1 number(s): "752162081"

Test #23:

score: 0
Accepted
time: 2125ms
memory: 31824kb

input:

995033 94

output:

130314865

result:

ok 1 number(s): "130314865"

Test #24:

score: 0
Accepted
time: 2075ms
memory: 31460kb

input:

901438 97

output:

809128292

result:

ok 1 number(s): "809128292"

Test #25:

score: 0
Accepted
time: 1968ms
memory: 31856kb

input:

993020 0

output:

926771801

result:

ok 1 number(s): "926771801"

Test #26:

score: 0
Accepted
time: 2130ms
memory: 31908kb

input:

1000000 100

output:

470305140

result:

ok 1 number(s): "470305140"