QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#131264 | #621. 多项式指数函数 | wunuowang | Compile Error | / | / | C++14 | 5.4kb | 2023-07-26 19:51:38 | 2023-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]
- 评测
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [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;
}
详细
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