QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#622704#1423. BinAfterlifeAC ✓3400ms39588kbC++204.3kb2024-10-09 00:26:332024-10-09 00:26:34

Judging History

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

  • [2024-10-09 00:26:34]
  • 评测
  • 测评结果:AC
  • 用时:3400ms
  • 内存:39588kb
  • [2024-10-09 00:26:33]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int mod=998244353;
inline int inc(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int dec(int x,int y){return x-y<0?x-y+mod:x-y;}
inline int mul(int x,int y){return (ll)x*y%mod;}
inline int qpow(int x,int y){
	int res=1;
	for(;y;y>>=1)res=y&1?mul(res,x):res,x=mul(x,x);
	return res;
}
inline int inv(int x){return qpow(x,mod-2);}

const int N=1<<20;
namespace NTT{
int re[N],w[2][N];
inline int getre(int n){
	int len=1,bit=0;
	while(len<n)len<<=1,++bit;
	for(int i=1;i<len;++i)re[i]=(re[i>>1]>>1)|((i&1)<<(bit-1));
	w[0][0]=w[1][0]=1,w[0][1]=qpow(3,(mod-1)/len),w[1][1]=inv(w[0][1]);
	for(int o=0;o<2;++o)for(int i=2;i<len;++i)
		w[o][i]=mul(w[o][i-1],w[o][1]);
	return len;
}
inline void NTT(int* a,int n,int o=0){
	for(int i=1;i<n;++i)if(i<re[i])swap(a[i],a[re[i]]);
	int R;
	for(int k=1;k<n;k<<=1)
		for(int i=0,t=k<<1,st=n/t;i<n;i+=t)
			for(int j=0,nw=0;j<k;++j,nw+=st)
				R=mul(a[i+j+k],w[o][nw]),a[i+j+k]=dec(a[i+j],R),a[i+j]=inc(a[i+j],R);
	if(o){
		R=inv(n);
		for(int i=0;i<n;++i)a[i]=mul(a[i],R);
	}
}

int t0[N],t1[N],t2[N];
inline void multi(const int* a,const int* b,int* c,int n,int m){
	if(n+m<=32){
		memset(c,0,sizeof(int)*(n+m+1));
		for(int i=0;i<=n;++i)
			for(int j=0;j<=m;++j)
				c[i+j]=inc(c[i+j],mul(a[i],b[j]));
		return;
	}
	int len=getre(n+m+1);
	memset(t0,0,sizeof(int)*len),memcpy(t0,a,sizeof(int)*(n+1));
	memset(t1,0,sizeof(int)*len),memcpy(t1,b,sizeof(int)*(m+1));
	NTT(t0,len),NTT(t1,len);
	for(int i=0;i<len;++i)t0[i]=mul(t0[i],t1[i]);
	NTT(t0,len,1);
	memcpy(c,t0,sizeof(int)*(n+m+1));
}
inline void inver(const int* a,int* b,int n){
	int len=1;
	while(len<=n)len<<=1;
	memset(t0,0,sizeof(int)*len),memcpy(t0,a,sizeof(int)*(n+1));
	memset(t1,0,sizeof(int)*(len<<1));
	memset(t2,0,sizeof(int)*(len<<1));
	t2[0]=inv(t0[0]);
	for(int k=1;k<=len;k<<=1){
		memcpy(t1,t0,sizeof(int)*k);
		getre(k<<1);
		NTT(t1,k<<1),NTT(t2,k<<1);
		for(int i=0;i<(k<<1);++i)t2[i]=mul(t2[i],dec(2,mul(t1[i],t2[i])));
		NTT(t2,k<<1,1);
		for(int i=k;i<(k<<1);++i)t2[i]=0;
	}
	memcpy(b,t2,sizeof(int)*(n+1));
}
} //namespace NTT

struct poly:public vector<int>{
	inline int time()const{return size()-1;}
	inline poly(int tim=0,int c=0){
		resize(tim+1);
		if(tim>=0)at(0)=c;
	}
    inline poly(int *l,int *r) {
        resize((r-l)+1);
        for(int i = 0;i < size();i++) at(i) = *(l + i);
    }
	inline poly operator%(const int& n)const{
		poly r(*this);
		r.resize(n);
		return r;
	}
	inline poly operator%=(const int& n){
		resize(n);
		return *this;
	}
	inline poly operator+(const poly& p)const{
		int n=time(),m=p.time();
		poly r(*this);
		if(n<m)r.resize(m+1);
		for(int i=0;i<=m;++i)r[i]=inc(r[i],p[i]);
		return r;
	}
	inline poly operator-(const poly& p)const{
		int n=time(),m=p.time();
		poly r(*this);
		if(n<m)r.resize(m+1);
		for(int i=0;i<=m;++i)r[i]=dec(r[i],p[i]);
		return r;
	}
	inline poly operator*(const poly& p)const{
		poly r(time()+p.time());
		NTT::multi(&((*this)[0]),&p[0],&r[0],time(),p.time());
		return r;
	}
	inline poly operator*(const int& k)const{
		poly r(*this);
		int n=time();
		for(int i=0;i<=n;++i)r[i]=mul(r[i],k);
		return r;
	}
	inline poly operator~()const{
		poly r(*this);
		reverse(r.begin(),r.end());
		return r;
	}
};

int f[1000005];
int n , k;
void solve(int l,int r) {
    if(l == r) {
        for(int i = (l + 1) / 2 ; i <= (l - i) + k && i < l; i++) {
            f[l] = (f[l] + 1LL * f[i] * f[l - i]) % mod;
        }
        // printf("%d %d\n",l,f[l]) ;
        return ;
    }
    int md = (l + r >> 1);
    solve(l , md);
    if(l != 1) {
        poly a(f + l , f + md) ;
        poly b(f + 1 , f + r - l) ;
        a = a * b;
        for(int i = md + 1 ; i <= r;i++) {
            f[i] = (f[i] + a[i - (l + 1)]) % mod;
        }
    }
    solve(md + 1 , r) ;
    poly a(f + l , f+md);
    poly b(f + md + 1 , f + r) ;
    a = a * b;
    for(int i = 0;i < a.size() && i + md + 1 <= n;i++) {
        // printf("on %d %d : %d %d: contri %d\n",l,md,md+1,r,i+l+md+1);
        if(i + l + md + 1 > r)
            f[i + l + md + 1] = (f[i + l + md + 1] + a[i]) % mod;
    }
    return ;
}
int main() {
     cin >> n >> k;
     f[1] = 1;
    solve(1 , n );
    cout << f[n] << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3624kb

input:

2 0

output:

1

result:

ok 1 number(s): "1"

Test #2:

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

input:

3 0

output:

1

result:

ok 1 number(s): "1"

Test #3:

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

input:

3 1

output:

2

result:

ok 1 number(s): "2"

Test #4:

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

input:

4 0

output:

2

result:

ok 1 number(s): "2"

Test #5:

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

input:

4 1

output:

3

result:

ok 1 number(s): "3"

Test #6:

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

input:

4 2

output:

5

result:

ok 1 number(s): "5"

Test #7:

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

input:

6 2

output:

23

result:

ok 1 number(s): "23"

Test #8:

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

input:

7 42

output:

132

result:

ok 1 number(s): "132"

Test #9:

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

input:

10 1

output:

400

result:

ok 1 number(s): "400"

Test #10:

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

input:

13 4

output:

42003

result:

ok 1 number(s): "42003"

Test #11:

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

input:

239 17

output:

385818773

result:

ok 1 number(s): "385818773"

Test #12:

score: 0
Accepted
time: 120ms
memory: 12728kb

input:

50216 58

output:

744498776

result:

ok 1 number(s): "744498776"

Test #13:

score: 0
Accepted
time: 3225ms
memory: 36600kb

input:

787788 78

output:

394429402

result:

ok 1 number(s): "394429402"

Test #14:

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

input:

5 92

output:

14

result:

ok 1 number(s): "14"

Test #15:

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

input:

88 79

output:

931161641

result:

ok 1 number(s): "931161641"

Test #16:

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

input:

749 77

output:

615055472

result:

ok 1 number(s): "615055472"

Test #17:

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

input:

2281 89

output:

282226588

result:

ok 1 number(s): "282226588"

Test #18:

score: 0
Accepted
time: 8ms
memory: 12204kb

input:

5765 35

output:

293680396

result:

ok 1 number(s): "293680396"

Test #19:

score: 0
Accepted
time: 76ms
memory: 12544kb

input:

43189 12

output:

805295564

result:

ok 1 number(s): "805295564"

Test #20:

score: 0
Accepted
time: 3141ms
memory: 36736kb

input:

806855 5

output:

593114139

result:

ok 1 number(s): "593114139"

Test #21:

score: 0
Accepted
time: 3268ms
memory: 39372kb

input:

994514 45

output:

678426421

result:

ok 1 number(s): "678426421"

Test #22:

score: 0
Accepted
time: 3301ms
memory: 39588kb

input:

999921 62

output:

752162081

result:

ok 1 number(s): "752162081"

Test #23:

score: 0
Accepted
time: 3349ms
memory: 39256kb

input:

995033 94

output:

130314865

result:

ok 1 number(s): "130314865"

Test #24:

score: 0
Accepted
time: 3334ms
memory: 38900kb

input:

901438 97

output:

809128292

result:

ok 1 number(s): "809128292"

Test #25:

score: 0
Accepted
time: 3198ms
memory: 39492kb

input:

993020 0

output:

926771801

result:

ok 1 number(s): "926771801"

Test #26:

score: 0
Accepted
time: 3400ms
memory: 39572kb

input:

1000000 100

output:

470305140

result:

ok 1 number(s): "470305140"