QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#474100#9120. Huge Segment TreePhantomThreshold#RE 11ms21300kbC++173.0kb2024-07-12 16:06:442024-07-12 16:06:44

Judging History

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

  • [2024-07-12 16:06:44]
  • 评测
  • 测评结果:RE
  • 用时:11ms
  • 内存:21300kb
  • [2024-07-12 16:06:44]
  • 提交

answer

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

namespace NTT{
	const int MOD=998244353,g=3,ig=332748118;
	const int MAXN=1077777;
	inline long long poww(long long x,long long y){
		long long ret=1;
		while (y){
			if (y&1) ret*=x,ret%=MOD;
			x*=x,x%=MOD;
			y>>=1;
		}
		return ret;
	}
	inline long long inv(long long x){return poww(x,MOD-2);}
	int R[MAXN];
	inline void fft(vector<long long> &a,int L,int ty){
		for (int i=0;i<L;i++) i>R[i]?swap(a[i],a[R[i]]):void(0);
		for (int i=1;i<L;i<<=1){
			long long w=poww(ty,(MOD-1)/(i<<1));
			for (int j=0;j<L;j+=(i<<1)){
				long long wn=1;
				for (int k=j;k<i+j;k++){
					long long t=wn*a[i+k]%MOD;
					a[i+k]=a[k]-t;a[i+k]<0?a[i+k]+=MOD:0;
					a[k]+=t;a[k]>=MOD?a[k]-=MOD:0;
					wn=wn*w%MOD;	
				}
			}
		}
	}
	inline vector<long long> mul(vector<long long> A,vector<long long> B){
		int L=1,n=A.size()-1,m=B.size()-1;
		while (L<=n+m) L<<=1;
		A.resize(L);
		B.resize(L);
		for (int i=1;i<L;i<<=1)
			for (int j=0;j<i;j++)
				R[i+j]=R[j]+L/(i<<1);
		fft(A,L,g);
		fft(B,L,g);
		vector<long long> ret(L);
		for (int i=0;i<L;i++) ret[i]=A[i]*B[i]%MOD;
		fft(ret,L,ig);
		long long invL=inv(L);
		for (int i=0;i<L;i++) ret[i]=ret[i]*invL%MOD;
		ret.resize(n+m+1);
		return ret;
	}
}

typedef long long ll;

const int maxn=1000000;
const ll mod=998244353;

inline void add(ll &A,ll B){A+=B;if (A>=mod) A-=mod;}
inline void sub(ll &A,ll B){A-=B;if (A<0) A+=mod;}

ll ksm(ll a,ll x){
	ll ret=1;
	for (;x;x>>=1,a=a*a%mod) if (x&1) ret=ret*a%mod;
	return ret;	
}
ll inv(ll a){return ksm(a,mod-2);}

ll fac[maxn+50];
ll ifac[maxn+50];

void prepare(){
	fac[0]=1;
	for (int i=1;i<=maxn;i++) fac[i]=fac[i-1]*i%mod;
	ifac[maxn]=inv(fac[maxn]);
	for (int i=maxn-1;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
//	
//	for (int i=0;i<=10;i++) cout << fac[i] << " ";
//	cout << endl;
//	
//	for (int i=0;i<=10;i++) cout << ifac[i] << " ";
//	cout << endl;
//	
}
ll C(ll n,ll m){
	if (m<0 || m>n) return 0;
	return fac[n]*ifac[m]%mod*ifac[n-m]%mod;	
}

ll K;

int main(){
	ios_base::sync_with_stdio(false);
	
	prepare();
	cin >> K;
	
	vector<ll> A(2*K-1);
	vector<ll> ans(2*K-1);
	for (ll c=0;c<=K-1;c++){
		
		ll coef=ksm(2,c);
		ll d=K-1-c;
		
		sub(ans[2],coef);
		add(ans[1],coef);
		
		add(A[2*d],coef);
		add(A[d+1],coef*2%mod);
		sub(A[d],coef*4%mod);
		
		add(A[2],coef);
		sub(A[1],coef*4%mod);
		add(A[0],coef*4%mod);
		
	}
	
	for (ll i=0;i<=2*K-2;i++) A[i]=A[i]*fac[i]%mod;
	
	reverse(A.begin(),A.end());
	vector<ll> tmp(2*K-1);
	for (ll i=0;i<=2*K-2;i++) tmp[i]=ifac[i];
	
	vector<ll> B=NTT::mul(A,tmp);
	B.resize(2*K-1);
	reverse(B.begin(),B.end());
	for (ll i=0;i<=2*K-2;i++) B[i]=B[i]*ifac[i]%mod;
	
//	vector<ll> B(2*K-1);
//	for (int i=0;i<=2*K-2;i++){
//		for (int j=i;j<=2*K-2;j++){
//			add(B[i],A[j]*C(j,i)%mod);
//		}
//	}
	
	for (int i=0;i<=2*K-2;i++) add(ans[i],B[i]);
	add(ans[1],ksm(2,K));
	
	for (int i=1;i<=2*K-2;i++) cout << ans[i] << " \n"[i==2*K-2];
	
	return 0;	
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2

output:

7 3

result:

ok 2 tokens

Test #2:

score: 0
Accepted
time: 7ms
memory: 20640kb

input:

3

output:

15 14 6 1

result:

ok 4 tokens

Test #3:

score: 0
Accepted
time: 7ms
memory: 20324kb

input:

4

output:

31 43 36 19 6 1

result:

ok 6 tokens

Test #4:

score: 0
Accepted
time: 7ms
memory: 20176kb

input:

5

output:

63 110 132 114 70 30 8 1

result:

ok 8 tokens

Test #5:

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

input:

6

output:

127 255 384 448 400 272 136 47 10 1

result:

ok 10 tokens

Test #6:

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

input:

7

output:

255 558 978 1401 1610 1478 1066 589 240 68 12 1

result:

ok 12 tokens

Test #7:

score: 0
Accepted
time: 7ms
memory: 20348kb

input:

8

output:

511 1179 2292 3803 5250 5987 5576 4183 2482 1137 388 93 14 1

result:

ok 14 tokens

Test #8:

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

input:

9

output:

1023 2438 5088 9398 14896 20038 22632 21250 16406 10282 5144 2006 588 122 16 1

result:

ok 16 tokens

Test #9:

score: 0
Accepted
time: 7ms
memory: 21300kb

input:

10

output:

2047 4975 10896 21772 38360 58724 77184 86312 81448 64324 42112 22576 9744 3304 848 155 18 1

result:

ok 18 tokens

Test #10:

score: 0
Accepted
time: 7ms
memory: 20612kb

input:

11

output:

4095 10070 22782 48209 92140 156292 232068 298744 330926 313422 252186 171122 97008 45368 17200 5155 1176 192 20 1

result:

ok 20 tokens

Test #11:

score: -100
Runtime Error

input:

500000

output:


result: