QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#356886#621. 多项式指数函数Nahidameow80 2355ms141724kbC++208.8kb2024-03-18 14:59:252024-03-18 14:59:26

Judging History

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

  • [2024-03-18 14:59:26]
  • 评测
  • 测评结果:80
  • 用时:2355ms
  • 内存:141724kb
  • [2024-03-18 14:59:25]
  • 提交

answer

#include<bits/stdc++.h>
//=========================================================
typedef long long ll;
typedef __int128 Int;
typedef unsigned long long ul;
typedef long double LD;
#define pd push_back
#define all(x) x.begin(),x.end()
#define allA(x,l,r) x+l,x+r+1
#define mpr std::make_pair
#define ve std::vector
#define mpre(v) v.insert(v.begin(),0)
#define lb lower_bound
//=========================================================
namespace Math{
	ll QP(ll x,ll y,ll mod){ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1)ans=ans*x%mod;return ans;}
	ll QA(ll x,ll y,ll mod){ll ans=0;for(;y;y>>=1,x=(x<<1)%mod)if(y&1)ans=(ans+x)%mod;return ans;}
	ll inv(ll x,ll mod){return QP(x,mod-2,mod);}
}
//=========================================================
namespace IO{
	const double eps=1e-8;
	const int BUFSIZE=1<<20;
	char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
	char tmp[BUFSIZE];int cnt=0;
	inline char getch(){if(is==it)it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);return is==it?EOF:*is++;}
	int readInt(){int x=0,y=0;char c=0;while(!isdigit(c))y|=c=='-',c=getch();while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getch();return !y?x:-x;}
	ll readLL(){ll x=0,y=0;char c=0;while(!isdigit(c))y|=c=='-',c=getch();while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getch();return !y?x:-x;}
	Int readInt128(){Int x=0;int y=0;char c=0;while(!isdigit(c))y|=c=='-',c=getch();while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getch();return !y?x:-x;}
	char readChar(){char c=0;while(!c||c==' '||c=='\n')c=getch();return c;}
	std::string readString(){std::string S;char c=0;while(!c||c==' '||c=='\n')c=getch();while(c!=' '&&c!='\n')S.pd(c),c=getch();return S;}
	LD readDouble(){LD x=0,d=1;int y=0;char c=0;while(!isdigit(c))y|=c=='-',c=getch();int cnt=0;bool flg=false;while(isdigit(c)){
		x=x*10+(c^48),flg|=(c^48),cnt+=flg,c=getch();if(cnt>=12)goto flg;}if(c=='.'){c=getch();while(isdigit(c)){d*=10,x+=(c^48)/d;flg|=(c^48),cnt+=flg;
		if(cnt>=12)goto flg;c=getch();}}flg:;return !y?x:-x;}

	void flush(){fwrite(tmp,1,cnt,stdout);cnt=0;}
	void putch(char c){tmp[cnt++]=c;if(cnt==BUFSIZE)flush();}
	void putint(int x){char Q[10];int tp=0;if(x<0)putch('-'),x=-x;if(x==0)putch('0');while(x)Q[tp++]=(x%10+'0'),x/=10;while(tp--)putch(Q[tp]);}
	void putInt128(Int x){char Q[45];int tp=0;if(x<0)putch('-'),x=-x;if(x==0)putch('0');while(x)Q[tp++]=(x%10+'0'),x/=10;while(tp--)putch(Q[tp]);}
	void putLL(ll x){char Q[20];int tp=0;if(x<0)putch('-'),x=-x;if(x==0)putch('0');while(x)Q[tp++]=(x%10+'0'),x/=10;while(tp--)putch(Q[tp]);}
	void putString(std::string x){for(auto p:x)putch(p);}
	void putDouble(LD x){if(x<0)x=-x,putch('-');if(fabs(x)<=eps)return putch(0);bool flg=false;LD d=1e10;LD l=std::min(LD(1e-10),1.0/std::max(LD(1),x));
		while(d>=l){if(d<=1){if(ll(x/d+d*1e-2)%10>0||flg)putch(ll(x/d+d*1e-2)%10+'0'),flg=true;}else{if(ll(x/d)%10>0||flg)putch(ll(x/d)%10+'0'),flg=true;
		}x-=ll(x/d+eps)*d; if(d==1){if(!flg)putch('0');putch('.');}d/=10;}}

	struct Basic{
		Basic &operator>>(int &A){A=IO::readInt();return (*this);}
		Basic &operator>>(ll &A){A=IO::readLL();return (*this);}
		Basic &operator>>(Int &A){A=IO::readInt128();return (*this);}
		Basic &operator>>(char &A){A=IO::readChar();return (*this);}
		Basic &operator>>(std::string &A){A=IO::readString();return (*this);}
		Basic &operator>>(double &A){A=IO::readDouble();return (*this);}
		Basic &operator>>(LD &A){A=IO::readDouble();return (*this);}
		Basic &operator>>(float &A){A=IO::readDouble();return (*this);}
		template<typename T1,typename T2>
		Basic &operator>>(std::pair<T1,T2>&v){(*this)>>v.first>>v.second;return (*this);}
		template<typename T,int d>
		Basic &operator>>(std::array<T,d> &v){for(auto &p:v)(*this)>>p;return (*this);}
		template<typename T>
		Basic &operator>>(std::vector<T> &v){for(auto &p:v)(*this)>>p;return (*this);}

		Basic &operator<<(const int &A){putint(A);return (*this);}
		Basic &operator<<(const char &A){putch(A);return (*this);}
		Basic &operator<<(const ll &A){putLL(A);return (*this);}
		Basic &operator<<(const Int &A){putInt128(A);return (*this);}
		Basic &operator<<(const std::string &A){putString(A);return (*this);}
		Basic &operator<<(const LD &A){putDouble(A);return (*this);}
		Basic &operator<<(const double &A){putDouble(A);return (*this);}
		Basic &operator<<(const float &A){putDouble(A);return (*this);}
		template<typename T>
		Basic &operator<<(const std::vector<T> &v){for(int i=0;i<v.size();i++)(*this)<<v[i]<<(v.size()==i+1?'\n':' ');return (*this);}

		void Flush(){flush();}
	}cin,cout;
}
//=========================================================
bool FileIfstream(std::string name){
	std::ifstream f(name.c_str());
	return f.good();
}
//=========================================================
const int mod=998244353,g=3;
//int add(int x,int y){x+=y;if(x>=mod)x-=mod;if(x<0)x+=mod;return x;}
//int mul(int x,int y){return 1ll*x*y%mod;}
//void add(int &x,int y){x+=y;if(x>=mod)x-=mod;if(x<0)x+=mod;}
const int N=4e6+10;
struct Finv{
	int fac[N],nfac[N],gi[N];
	void init(){
		fac[0]=1;for(int i=1;i<=N-10;i++)fac[i]=1ll*fac[i-1]*i%mod;
		nfac[N-10]=Math::inv(fac[N-10],mod);
		for(int i=N-11;~i;i--)nfac[i]=1ll*nfac[i+1]*(i+1)%mod;
		for(int i=2;i<=N-10;i<<=1){
			int G=Math::QP(g,(mod-1)/i,mod);
			gi[i>>1]=1;
			for(int j=(i>>1)+1;j<i;j++)
				gi[j]=1ll*gi[j-1]*G%mod;
		}
	}
	int inv(int x){return 1ll*nfac[x]*fac[x-1]%mod;}
	int C(int x,int y){return x<0||y<0||x<y?0:1ll*fac[x]*nfac[y]%mod*nfac[x-y]%mod;}
}Ft;
struct Poly{
	std::vector<int>v;
	inline void read(int n){v.resize(n+1);IO::cin>>v;}
	inline void write(){IO::cout<<v;}
	
	void clear(int n=-1){while(v.size()>n+1)v.pop_back();}
	void reverse(){std::reverse(all(v));}
	int size(){return int(v.size())-1;}
	
	inline int operator [](const int &i)const{return 
		(v.size()<=i)?0:v[i];}
	inline int& operator [](const int &i){(v.size()<=i
		&&(v.resize(i+1),0));return v[i];}
	
	inline int GetLimit(int n){int lim=0;while((1<<lim)<=n)lim++;return lim;}
	inline void NTT(Poly &f,const int &n){
		for(int i=n>>1;i;i>>=1)
			for(int j=0;j<n;j+=(i<<1))
				for(int k=0,x,y;k<i;k++){
					x=f[j|k],y=f[i|j|k],
					f[j|k]=x+y-(x+y>=mod?mod:0),
					f[i|j|k]=1ll*Ft.gi[i|k]*(x-y+(x-y<0?mod:0))%mod;
				}
	}
	inline void INTT(Poly &f,const int &n){
		for(int i=1;i<n;i<<=1)
			for(int j=0;j<n;j+=(i<<1))
				for(int k=0,x,y;k<i;k++){
					x=f[j|k],y=1ll*Ft.gi[i|k]*f[i|j|k]%mod,
					f[j|k]=x+y-(x+y>=mod?mod:0),f[i|j|k]=x-y+(x-y<0?mod:0);
				}
		int I=Math::inv(n,mod);
		std::reverse(f.v.begin()+1,f.v.begin()+n);
		for(int i=0;i<n;i++)f[i]=1ll*f[i]*I%mod;
	}
	
	inline Poly convolution(Poly A,Poly B){
		int L=GetLimit(A.size()+B.size());
		NTT(A,1<<L);NTT(B,1<<L);for(int i=0;i<(1<<L);i++)A[i]=1ll*A[i]*B[i]%mod;
		INTT(A,1<<L);return A;
	}
	inline void inverse(Poly &F,int n){
		if(n==1)return F[0]=Math::inv(v[0],mod),void();
		inverse(F,n+1>>1);int lim=1;
		for(;lim<(n<<1);lim<<=1);	
		Poly G=(*this);G.clear(n-1);
		NTT(F,lim);NTT(G,lim);
		for(int i=0;i<lim;i++)
			F[i]=1ll*(2ll-1ll*G[i]*F[i]%mod+mod)*F[i]%mod;
		INTT(F,lim);
		F.clear(n-1);
	}
	inline void _dif(Poly &F,int n){
		for(int i=0;i<n;i++)
			F[i]=1ll*(*this)[i+1]*(i+1)%mod;
	}
	inline void _int(Poly &F,int n){
		F[0]=0;
		for(int i=1;i<=n;i++)
			F[i]=1ll*(*this)[i-1]*Ft.inv(i)%mod;
	}
	inline void _ln(Poly &F,int n){
		assert((*this)[0]==1);
	//	((*this).Inv()*(*this).Dif()).Int().write();
		F=((*this).Dif()*(*this).Inv()).Int();
		F.clear(n);
	}
	inline void _exp(Poly &F,int n){
		if(n==1)return F[0]=1,void();
		_exp(F,n+1>>1);
		Poly A;A=F.Ln();
		for(int i=0;i<n;i++)A[i]=0ll+(*this)[i]-A[i]+((*this)[i]-A[i]<0?mod:0);
		A[0]=(A[0]+1-(A[0]+1>=mod?mod:0));
		F=F*A,F.clear(n-1);
	}
	
	inline Poly Times(Poly &y){
		Poly A=convolution((*this),y);
		A.clear(size()+y.size());
		return A;
	}
	inline Poly Inv(){
		Poly T;
		inverse(T,size()+1);
		return T;
	}
	inline Poly Int(){
		Poly T;
		_int(T,size()+1);
		return T;
	}
	inline Poly Dif(){
		Poly T;
		_dif(T,size());
		return T;
	}
	inline Poly Ln(){
		assert((*this)[0]==1);
		Poly T;
		_ln(T,size());
		return T;
	}
	inline Poly Exp(int n=-1){
		assert((*this)[0]==0);
		Poly T;int P=size()+1;
		_exp(T,P<<1);
		if(n==-1)T.clear(P-1);
		else T.clear(n);
		clear(P-1);
		return T;
	}
	
	inline Poly operator *(Poly y){return Times(y);}
	
	inline void operator *=(Poly y){(*this)=(*this)*y;}
};
void solve(){
	//don't forget to open long long
	int n;IO::cin>>n;n--;
	Poly A;A.read(n);
	for(auto &p:A.v)p%=mod;
	A.Exp().write();
}
int main(){
#ifndef ONLINE_JUDGE
	if(!FileIfstream("IO.in")){
		freopen("IO.in","w",stdout);
		return 0;
	}
	freopen("IO.in","r",stdin);
	freopen("IO.out","w",stdout);
#endif
	//std::ios::sync_with_stdio(false);
	//std::cin.tie(0);
	//std::cout.tie(0);
	int T=1;
	Ft.init();
	while(T--)solve();

	IO::cout.Flush();
	return 0;
}



詳細信息

Test #1:

score: 20
Accepted
time: 45ms
memory: 43320kb

input:

100
0 158447743 737554986 671332600 489297184 754299210 115728600 816221630 819073359 691660913 910093246 562505672 355119917 385019894 611338034 123976316 122342952 82142434 796101450 994778874 575255638 493217967 652609142 662045597 783871340 470398790 241710709 754059035 534582325 836438174 95789...

output:

1 158447743 989903074 918187254 200068193 455062373 11196740 759336019 312075964 992242039 123230223 144998958 189062409 420150911 170942299 432890803 760087114 639614944 787205333 63667632 243571846 141993017 450288335 173318832 743144111 879389773 95666186 453410000 569486107 512729334 226210545 5...

result:

ok 100 numbers

Test #2:

score: 20
Accepted
time: 59ms
memory: 45880kb

input:

5000
0 354399910 26360255 630255958 717224815 366941345 333979504 905420494 38176634 475666562 611197455 433060682 509600868 845217181 520468365 529689763 431747498 192834976 685184103 287994809 273221518 522219732 427553800 10872482 525061651 448069946 183539744 610476003 840167561 241104955 404100...

output:

1 354399910 51676417 184411965 928033808 589971658 936383703 745898312 943454394 65252947 270867254 772620225 995104944 58521883 96491645 326592384 283913887 140742590 960115688 684602174 623426872 184484323 952879775 315489867 167038509 580362327 164714100 833258994 345402076 261957154 469710461 98...

result:

ok 5000 numbers

Test #3:

score: 20
Accepted
time: 88ms
memory: 47600kb

input:

30000
0 147199510 293972908 780683378 633744119 800282266 162025013 919460711 939176222 298044997 277962122 729446209 455723129 756791462 84697115 579989768 945113433 549318980 229266945 869577376 103161009 960973464 440149102 836285074 687333626 638404974 184096947 370164754 454531549 142629528 150...

output:

1 147199510 30930552 734023222 564008583 299902819 450980389 806779390 654937901 981162061 206882721 35851319 707998765 357594654 305814262 734562024 591099032 543969413 539432668 154163976 451201740 856569012 898961429 732819402 243444529 673245321 601964526 206333661 876679409 438174247 903706710 ...

result:

ok 30000 numbers

Test #4:

score: 20
Accepted
time: 285ms
memory: 57948kb

input:

100000
0 279349013 196667718 617497154 78288698 996674429 180463729 304956112 173800460 352061138 224505321 119706982 726737325 564797383 757014824 888433954 747100108 723246918 645172013 184990722 321964667 456686646 138153830 701558524 317746193 650472945 49496183 864461799 982372868 582778782 242...

output:

1 279349013 426120005 205100346 421201310 474118168 879116053 749708347 23319122 872190753 903275287 797670709 327019687 707029564 46014243 838268797 28223150 48499086 927009654 52188573 200586020 4624185 827007182 201682326 552029133 820855946 97607062 601649418 37529652 24405665 116064030 62051631...

result:

ok 100000 numbers

Test #5:

score: 0
Wrong Answer
time: 2355ms
memory: 141724kb

input:

1000000
0 204517192 162156394 729093416 352181074 335898409 357987855 386581690 26622360 437289663 34104646 938411413 659876244 293619518 291093969 909364118 179765868 89417259 632261731 375051702 493701794 771716785 682264158 329653513 86558030 9195128 957504298 22555222 384175297 128022431 5957444...

output:

499122177 102258596 309735930 258739565 725907726 877164254 125468287 865938310 61678131 867534115 517561679 566552256 544925730 948570634 205294216 633836304 468142862 403750040 573471980 347300212 551573367 621698699 407138300 804542585 728832755 897926506 137795224 483946287 625032481 843459678 3...

result:

wrong answer 1st numbers differ - expected: '1', found: '499122177'