QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#131264#621. 多项式指数函数wunuowangCompile Error//C++145.4kb2023-07-26 19:51:382023-07-26 19:51:41

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-26 19:51:41]
  • 评测
  • [2023-07-26 19:51:38]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pd push_back
#define all(x) x.begin(),x.end()
//==============================================================
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 inv(ll x,ll mod){return QP(x,mod-2,mod);}
//==============================================================
namespace IO{
	int readInt(){
		int x=0,y=0;char c=0;
		while(!isdigit(c))y|=c=='-',c=getchar();
		while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
		return !y?x:-x;
	}
}
//===============================================================
const int N=3e6+10;
const int g=3,mod=998244353,gi=inv(3,mod);
int w[40]={0,998244352,911660635,372528824,929031873,452798380,922799308,781712469,476477967,
		  166035806,258648936,584193783,63912897,350007156,666702199,968855178,629671588,24514907,
		  996173970,363395222,565042129,733596141},
	w0[40]={0,998244352,86583718,509520358,337190230,87557064,609441965,135236158,304459705,685443576,
			381598368,335559352,129292727,358024708,814576206,708402881,283043518,3707709,121392023,
			704923114,950391366,428961804};
//ll g1=QP(opt==1?g:gi,(mod-1)/(i<<1),mod);
void init1(){
	for(int i=1,p=1;i<=2e6;i<<=1,p++)w[p]=QP(g,(mod-1)/(i<<1),mod);
	for(int i=1,p=1;i<=2e6;i<<=1,p++)w0[p]=QP(gi,(mod-1)/(i<<1),mod);
}
vector<int> rev;
void Resize(int n){rev.resize(n<<1);}
namespace Math{
	int fac[N],nfac[N];
	int Iv[N];
	void initfac(){
		fac[0]=1;for(int i=1;i<=N-10;i++)fac[i]=1ll*fac[i-1]*i%mod;
		nfac[N-10]=inv(fac[N-10],mod);for(int i=N-11;~i;i--)nfac[i]=1ll*nfac[i+1]*(i+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;}
	void initinv(){
		Iv[1]=1;
		for(int i=2;i<=N-10;i++)
			Iv[i]=1ll*(-1ll*Iv[mod%i]*(mod/i)%mod+mod)%mod;
	}
}
struct Poly{
	vector<int> v;
	inline void read(int n){v.resize(n+1);for(int i=0;i<=n;i++){v[i]=IO::readInt();if(v[i]>=mod)v[i]-=mod;};}
	inline void write(int n){for(int i=0;i<=n;i++)printf("%d ",v[i]);puts("");return;}
	inline void debug(){for(auto y:v)printf("%d ",y);puts("");return;} 
	//=========================================================================
	inline void clear(int n){while(v.size()>n+1)v.pop_back();} 
	//=========================================================================
	inline int operator [](const int &i)const{
		if(v.size()<=i)return 0;
		else return v[i];
	}inline int& operator [](const int &i){
		if(v.size()<=i)v.resize(i+1);
		return v[i];
	}
	//==========================================================================
	inline int init2(int n,int m){
		int lim=0; 
		while((1<<lim)<=n+m)lim++;
		for(int i=0;i<(1<<lim);i++)rev[i]=(rev[i>>1]>>1)|((i&1)?(1<<lim-1):0);
		return lim;
	}
	/*inline int add(ll x,const int &y){
		x+=y;if(x>=mod)x-=mod;
		if(x<0)x+=mod;
		return x;
	}*/
	//==========================================================================
	inline void NTT(Poly &f,const int &n,const int &opt){
		for(int i=0;i<n;i++)if(i<rev[i])swap(f[i],f[rev[i]]);
		for(int i=1,p0=1;i<n;i<<=1,p0++){
			ll g1=opt?w[p0]:w0[p0];//QP(opt==1?g:gi,(mod-1)/(i<<1),mod);
			for(int j=0;j<n;j+=(i<<1))
				for(ll k=0,gk=1;k<i;k++,gk=1ll*gk*g1%mod){
					ll x=f[j+k],y=1ll*gk*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); 
				}
		}//f.debug();
		if(!opt){
			int Inv=inv(n,mod);
			for(int i=0;i<n;i++)f.v[i]=1ll*f.v[i]*Inv%mod;
		}
	}inline Poly convolution(Poly A,Poly B){
		int lim=init2(A.v.size()-1,B.v.size()-1);
	//	A.debug();B.debug();
		NTT(A,1<<lim,1);NTT(B,1<<lim,1);
	//	A.debug();B.debug();
		for(int i=0;i<(1<<lim);i++)A[i]=1ll*A[i]*B[i]%mod;
		NTT(A,(1<<lim),0);
	//	for(auto y:A.v)printf("%d ",y);puts("");
		return A;
	}
	inline void Ginv(Poly &S,int n){
		if(n==1)return S[0]=inv(v[0],mod),void();
		Ginv(S,n+1>>1);int lim=1,len=0;
		for(;lim<(n<<1);lim<<=1,len++);	
	//	lim=1<<len;
		for(int i=1;i<lim;i++)
			rev[i]=(rev[i>>1]>>1)|((i&1)?(1<<len-1):0);
		Poly A;
		for(int i=n;~i;i--)A[i]=(*this)[i];
		NTT(A,lim,1);NTT(S,lim,1);
		for(int i=0;i<lim;i++)
			S[i]=1ll*(2ll-1ll*A[i]*S[i]%mod+mod)*S[i]%mod;
		NTT(S,lim,0);
		S.clear(n-1);
	}inline Poly Inv(){
		Poly ans;
		Ginv(ans,v.size());
		ans.clear(v.size()-1);
		return ans;
	}inline Poly DifCalc(){
		Poly S;
		for(int i=0;i<v.size()-1;i++)
			S[i]=1ll*v[i+1]*(i+1)%mod;
		return S;
	}inline Poly IntCalc(){
		Poly S;S[0]=0;
		for(int i=0;i<v.size();i++)
			S[i+1]=1ll*v[i]*Math::Iv[i+1]%mod;
		return S;
	}inline Poly ln(){
		assert(v[0]==1);
		Poly S=((*this).DifCalc()*(*this).Inv()).IntCalc();
		S.clear(v.size()-1);
		return S;
	}inline void Gexp(Poly &S,int n){
		if(n==1)return S[0]=1,void();
		Gexp(S,n+1>>1);
		Poly A=S.ln();
		for(int i=0;i<n;i++)A[i]=1ll*(0ll+(*this)[i]+(i==0)-A[i]+mod)%mod;
		S=S*A;S.clear(n-1);
//		S.debug();
	}
	inline Poly exp(){
		Poly ans;//int lim=1;
		//for(;lim<=v.size();lim<<=1);
		Gexp(ans,v.size()<<1);
		ans.clear(v.size()-1);
		return ans;
	}
	//==========================================================================
	inline Poly operator * (const Poly &y){
		Poly ans=convolution((*this),y);
		as.clear(((*this).v.size()-1)+(y.v.size()-1));
		return ans;
	}
};int n,m;Poly x;
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	//init1();
	Resize(N);Math::initinv();
//	for(int i=0;i<=30;i++)cout<<w0[i]<<' ';
	n=IO::readInt();n--;
	x.read(n);
	x.exp().write(n);
	return 0;
}

Details

answer.code: In member function ‘Poly Poly::operator*(const Poly&)’:
answer.code:152:17: error: ‘as’ was not declared in this scope; did you mean ‘abs’?
  152 |                 as.clear(((*this).v.size()-1)+(y.v.size()-1));
      |                 ^~
      |                 abs