QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#110279#4472. 珍珠xiaoyaowudi100 ✓44ms16624kbC++175.6kb2023-06-01 13:11:422023-06-01 13:11:45

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-01 13:11:45]
  • 评测
  • 测评结果:100
  • 用时:44ms
  • 内存:16624kb
  • [2023-06-01 13:11:42]
  • 提交

answer

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using ll=long long;
namespace polynomial
{
	constexpr int P(998244353),N(200010),PR(3),APR((P+1)/PR);
	int ws[2][N<<2],fn,fb,inv[N<<2],rev[N<<2],fac[N<<2],ifac[N<<2];
	int fast_pow(int a,int b){int ans(1),off(a);while(b){if(b&1) ans=1ll*ans*off%P;off=1ll*off*off%P;b>>=1;}return ans;}
	void init_poly_weights(int len)
	{
		fn=1,fb=0;while(fn<(len<<1)) fn<<=1,++fb;
		inv[1]=1;for(int i(2);i<=fn;++i) inv[i]=1ll*(P-P/i)*inv[P%i]%P;
		fac[0]=ifac[0]=1;for(int i(1);i<=fn;++i) fac[i]=1ll*fac[i-1]*i%P,ifac[i]=1ll*ifac[i-1]*inv[i]%P;
		for(int i(0);i<fn;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(fb-1));
		for(int mid((fn>>1)),j0(fast_pow(PR,(P-1)/(mid<<1))),j1(fast_pow(APR,(P-1)/(mid<<1)));mid>=1;mid>>=1,j0=1ll*j0*j0%P,j1=1ll*j1*j1%P)
		for(int i(0),w0(1),w1(1);i<mid;++i,w0=1ll*w0*j0%P,w1=1ll*w1*j1%P) ws[0][i+mid]=w0,ws[1][i+mid]=w1;
	}
	using poly=std::vector<int>;
	int redu(int k){return k>=P?k-P:k;}
	poly operator+(const poly &a,const poly &b)
	{
		poly ret(b);if(ret.size()<a.size()) ret.resize(a.size());
		for(int i(0);i<a.size();++i) ret[i]=redu(ret[i]+a[i]);
		return ret;
	}
	unsigned long long tt[N<<2];
	int ntt_bits(int k){return std::__lg(std::max(k-1,1))+1;}
	void NTT(poly &p,int V)
	{
		int bts(ntt_bits(p.size()));if(p.size()!=(1<<bts)) p.resize((1<<bts));
		int* w(ws[(V==1)?0:1]),len(1<<bts);for(int i(0);i<len;++i) tt[i]=p[rev[i]>>(fb-bts)];
		unsigned long long t1,t2;
		for(int l(2);l<=len;l<<=1)
			for(int j(0),mid=(l>>1);j<len;j+=l)
				for(int i(0);i<mid;++i) t1=tt[j+i],t2=tt[j+i+mid]*w[mid+i]%P,tt[j+i]=t1+t2,tt[j+i+mid]=P+t1-t2;
		if(V==1) for(int i(0);i<len;++i) p[i]=tt[i]%P;
		else for(int i(0),j(inv[len]);i<len;++i) p[i]=tt[i]%P*j%P;
	}
	poly operator*(const poly &a,const poly &b)
	{
		static poly p1,p2;poly ret;
		p1=a,p2=b;int len(a.size()+b.size()-1),ff(1<<ntt_bits(len));
		p1.resize(ff),p2.resize(ff),ret.resize(ff);
		NTT(p1,1);NTT(p2,1);
		for(int i(0);i<ff;++i) ret[i]=1ll*p1[i]*p2[i]%P;
		NTT(ret,-1);ret.resize(len);return ret;
	}
	poly poly_inv(const poly &a)
	{
		int l(a.size());if(l==1){poly ret(1);ret[0]=fast_pow(a[0],P-2);return ret;}
		poly g0(a);g0.resize((l+1)>>1);g0=poly_inv(g0);int t(g0.size()),tb(ntt_bits(t<<1));
		poly f(a),g(g0);f.resize(1<<tb);g0.resize(1<<tb);NTT(f,1);NTT(g0,1);
		for(int i(0);i<(1<<tb);++i) f[i]=(1+1ll*(P-f[i])*g0[i])%P;
		NTT(f,-1);f.erase(f.begin(),f.begin()+t);f.resize(1<<tb);
		NTT(f,1);for(int i(0);i<(1<<tb);++i) f[i]=1ll*f[i]*g0[i]%P;
		NTT(f,-1);g.resize(l);std::copy(f.begin(),f.begin()+l-t,g.begin()+t);return g;
	}
	poly poly_ln(const poly &a)
	{
		int l(a.size());static poly p1;
		p1.resize(l-1);for(int i(1);i<l;++i) p1[i-1]=1ll*i*a[i]%P;
		p1=p1*poly_inv(a);p1.resize(l-1);poly ret(l);
		for(int i(1);i<l;++i) ret[i]=1ll*inv[i]*p1[i-1]%P;ret[0]=0;
		return ret;
	}
	poly poly_exp(const poly &a)
	{
		int l(a.size());if(l==1){poly ret(1);ret[0]=1;return ret;}
		poly g0(a);g0.resize((l+1)>>1);g0=poly_exp(g0);static poly g1,g2;g1=g0;g1.resize(l);g1=poly_ln(g1);g2=a;
		int ff(2<<ntt_bits(l));g0.resize(ff);g1.resize(ff);poly ret(ff);g2.resize(ff);
		NTT(g0,1);NTT(g1,1);NTT(g2,1);
		for(int i(0);i<ff;++i) ret[i]=1ll*g0[i]*(1-g1[i]+g2[i]+P)%P;
		NTT(ret,-1);ret.resize(l);return ret;
	}
	poly poly_pow(const poly &a,int k)
	{
		int l(a.size());
		if(!k){poly r(l);r[0]=1;return r;}
		int i(0);while(i<l && !a[i]) ++i;
		if(1ll*i*k>=l) return poly(l);
		poly f(a.begin()+i,a.begin()+i+l-i*k);
		int t(f[0]),_t(fast_pow(t,P-2));
		for(int &v:f) v=1ll*_t*v%P;t=fast_pow(t,k);
		f=poly_ln(f);
		for(int &v:f) v=1ll*v*k%P;
		f=poly_exp(f);
		for(int &v:f) v=1ll*t*v%P;
		f.resize(l);
		std::rotate(f.begin(),f.begin()+l-i*k,f.end());
		return f;
	}
	poly poly_shift(poly a,int k)
	{
		int l(a.size());
		poly tr(l);
		for(int i(0),j(1);i<l;++i,j=1ll*j*k%P) tr[i]=1ll*j*ifac[i]%P;
		for(int i(0);i<l;++i) a[i]=1ll*fac[i]*a[i]%P;
		std::reverse(a.begin(),a.end());
		a=a*tr;a.resize(l);std::reverse(a.begin(),a.end());
		for(int i(0);i<l;++i) a[i]=1ll*ifac[i]*a[i]%P;
		return a;
	}
}
using polynomial::poly;
using polynomial::init_poly_weights;
using polynomial::operator+;
using polynomial::operator*;
using polynomial::init_poly_weights;
using polynomial::poly_inv;
using polynomial::poly_ln;
using polynomial::poly_exp;
using polynomial::poly_pow;
using polynomial::poly_shift;
using polynomial::ifac;
using polynomial::fac;
using polynomial::inv;
constexpr int N(1e5+10),p(998244353),_2((p+1)/2);
int fp(int a,int b){int ans(1),off(a);while(b){if(b&1) ans=1ll*ans*off%p;off=1ll*off*off%p;b>>=1;}return ans;}
int main()
{
	int D,n,m;std::cin>>D>>n>>m;init_poly_weights(D+1);
	if(m*2>n){std::cout<<"0"<<std::endl;return 0;}
	int l(std::min(D,n-2*m));
	poly F(D+1),G(D+1);
	for(int i(D-l);i<=D;++i) F[i]=1ll*fac[D]*ifac[i]%p;
	for(int i(0);i<=D;++i) G[i]=(i&1)?p-ifac[i]:ifac[i];
	F=F*G;F.resize(D+1);
	for(int j(D),t(1);j>=0;--j,t=2*t%p) F[j]=1ll*F[j]*t%p*ifac[D-j]%p;
	// for(int v:F) std::cout<<v<<" ";std::cout<<std::endl;
	F=poly_shift(F,1);
	// for(int v:F) std::cout<<v<<" ";std::cout<<std::endl;
	static int ps[N],val[N];int pc(0);static bool vis[N];val[1]=1;
	for(int i(2);i<=D;++i)
	{
		if(!vis[i]) val[i]=fp(i,n),ps[++pc]=i;
		for(int j(1);j<=pc && ps[j]*i<=D;++j)
		{
			val[ps[j]*i]=1ll*val[ps[j]]*val[i]%p;
			vis[ps[j]*i]=true;
			if((i%ps[j])==0) break;
		}
	}
	int ans(0);
	for(int i(0);i<=D;++i)
	{
		int t(D-i*2);
		if(t<0 && n&1) ans=(ans+1ll*(p-val[std::abs(t)])*F[i])%p;
		else ans=(ans+1ll*val[std::abs(t)]*F[i])%p;
	}
	std::cout<<1ll*ans*fp(_2,D)%p<<std::endl;
	return 0;
}

詳細信息

Test #1:

score: 4
Accepted
time: 2ms
memory: 3508kb

input:

2 7 3

output:

128

result:

ok 1 number(s): "128"

Test #2:

score: 4
Accepted
time: 2ms
memory: 3524kb

input:

2 20 9

output:

1048576

result:

ok 1 number(s): "1048576"

Test #3:

score: 4
Accepted
time: 0ms
memory: 3520kb

input:

99 97 30

output:

893559494

result:

ok 1 number(s): "893559494"

Test #4:

score: 4
Accepted
time: 2ms
memory: 3572kb

input:

100 97 29

output:

870441375

result:

ok 1 number(s): "870441375"

Test #5:

score: 4
Accepted
time: 2ms
memory: 3504kb

input:

97 100 16

output:

114531619

result:

ok 1 number(s): "114531619"

Test #6:

score: 4
Accepted
time: 2ms
memory: 3568kb

input:

98 98 38

output:

910698957

result:

ok 1 number(s): "910698957"

Test #7:

score: 4
Accepted
time: 2ms
memory: 3532kb

input:

100 99 30

output:

267167918

result:

ok 1 number(s): "267167918"

Test #8:

score: 4
Accepted
time: 1ms
memory: 3896kb

input:

4000 3998 602

output:

267823033

result:

ok 1 number(s): "267823033"

Test #9:

score: 4
Accepted
time: 3ms
memory: 3916kb

input:

3999 3998 478

output:

7661427

result:

ok 1 number(s): "7661427"

Test #10:

score: 4
Accepted
time: 3ms
memory: 3976kb

input:

4000 3999 18

output:

46680613

result:

ok 1 number(s): "46680613"

Test #11:

score: 4
Accepted
time: 3ms
memory: 3900kb

input:

4000 3998 683

output:

689956672

result:

ok 1 number(s): "689956672"

Test #12:

score: 4
Accepted
time: 3ms
memory: 3912kb

input:

3998 3998 1743

output:

625630497

result:

ok 1 number(s): "625630497"

Test #13:

score: 4
Accepted
time: 2ms
memory: 3504kb

input:

300 999999997 499999880

output:

311178114

result:

ok 1 number(s): "311178114"

Test #14:

score: 4
Accepted
time: 2ms
memory: 3540kb

input:

297 999999999 499999955

output:

111728734

result:

ok 1 number(s): "111728734"

Test #15:

score: 4
Accepted
time: 1ms
memory: 3576kb

input:

298 999999998 499999978

output:

873407954

result:

ok 1 number(s): "873407954"

Test #16:

score: 4
Accepted
time: 40ms
memory: 16520kb

input:

100000 999999998 0

output:

403169128

result:

ok 1 number(s): "403169128"

Test #17:

score: 4
Accepted
time: 35ms
memory: 16512kb

input:

99999 100000 1

output:

520922757

result:

ok 1 number(s): "520922757"

Test #18:

score: 4
Accepted
time: 34ms
memory: 16524kb

input:

99998 99998 2

output:

776350879

result:

ok 1 number(s): "776350879"

Test #19:

score: 4
Accepted
time: 32ms
memory: 16624kb

input:

99998 999999998 499972261

output:

805937760

result:

ok 1 number(s): "805937760"

Test #20:

score: 4
Accepted
time: 42ms
memory: 16620kb

input:

99997 999999999 499975678

output:

265933807

result:

ok 1 number(s): "265933807"

Test #21:

score: 4
Accepted
time: 35ms
memory: 16528kb

input:

100000 1000000000 499958129

output:

59384653

result:

ok 1 number(s): "59384653"

Test #22:

score: 4
Accepted
time: 44ms
memory: 16532kb

input:

99998 999999999 499978565

output:

897679746

result:

ok 1 number(s): "897679746"

Test #23:

score: 4
Accepted
time: 37ms
memory: 16520kb

input:

100000 999999999 499970692

output:

169325977

result:

ok 1 number(s): "169325977"

Test #24:

score: 4
Accepted
time: 36ms
memory: 16596kb

input:

99997 1000000000 499976402

output:

562099965

result:

ok 1 number(s): "562099965"

Test #25:

score: 4
Accepted
time: 39ms
memory: 16556kb

input:

99997 1000000000 499978285

output:

681053406

result:

ok 1 number(s): "681053406"

Extra Test:

score: 0
Extra Test Passed