QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#85070 | #5685. 快速 LCM 变换 | myee | AC ✓ | 1113ms | 152820kb | C++11 | 29.8kb | 2023-03-06 22:21:18 | 2023-03-06 22:22:47 |
Judging History
answer
// 那就是希望。
// 即便需要取模,也是光明。
#include <algorithm>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
T ans=1%mod;
while(index)
{
if(index&1)ans=ans*base%mod;
base=base*base%mod,index>>=1;
}
return ans;
}
namespace ConstMod
{
template<const ullt p>
class mod_ullt
{
private:
ullt v;
inline ullt chg(ullt w){return(w<p)?w:w-p;}
inline mod_ullt _chg(ullt w){mod_ullt ans;ans.v=(w<p)?w:w-p;return ans;}
public:
mod_ullt():v(0){}
mod_ullt(ullt v):v(v%p){}
bol empty(){return!v;}
inline ullt val(){return v;}
friend bol operator<(mod_ullt a,mod_ullt b){return a.v<b.v;}
friend bol operator>(mod_ullt a,mod_ullt b){return a.v>b.v;}
friend bol operator<=(mod_ullt a,mod_ullt b){return a.v<=b.v;}
friend bol operator>=(mod_ullt a,mod_ullt b){return a.v>=b.v;}
friend bol operator==(mod_ullt a,mod_ullt b){return a.v==b.v;}
friend bol operator!=(mod_ullt a,mod_ullt b){return a.v!=b.v;}
inline friend mod_ullt operator+(mod_ullt a,mod_ullt b){return a._chg(a.v+b.v);}
inline friend mod_ullt operator-(mod_ullt a,mod_ullt b){return a._chg(a.v+a.chg(p-b.v));}
inline friend mod_ullt operator*(mod_ullt a,mod_ullt b){return a.v*b.v;}
friend mod_ullt operator/(mod_ullt a,mod_ullt b){return b._power(p-2)*a.v;}
friend mod_ullt operator^(mod_ullt a,ullt b){return a._power(b);}
inline mod_ullt operator-(){return _chg(p-v);}
mod_ullt sqrt()
{
if(power(v,(p-1)>>1,p)!=1)return 0;
mod_ullt b=1;do b++;while(b._power((p-1)>>1)==1);
ullt t=p-1,s=0,k=1;while(!(t&1))s++,t>>=1;
mod_ullt x=_power((t+1)>>1),e=_power(t);
while(k<s)
{
if(e._power(1llu<<(s-k-1))!=1)x*=b._power((1llu<<(k-1))*t);
e=_power(p-2)*x*x,k++;
}
return _min(x,-x),x;
}
mod_ullt inv(){return _power(p-2);}
mod_ullt _power(ullt index){mod_ullt ans(1),w(v);while(index){if(index&1)ans*=w;w*=w,index>>=1;}return ans;}
voi read(){v=0;chr c;do c=getchar();while(c>'9'||c<'0');do v=(c-'0'+v*10)%p,c=getchar();while(c>='0'&&c<='9');v%=p;}
voi print()
{
static chr C[20];uint tp=0;
ullt w=v;do C[tp++]=w%10+'0',w/=10;while(w);
while(tp--)putchar(C[tp]);
}
voi println(){print(),putchar('\n');}
mod_ullt operator++(int){mod_ullt ans=*this;return v=chg(v+1),ans;}
public:
inline ullt&operator()(){return v;}
inline mod_ullt&operator+=(mod_ullt b){return*this=_chg(v+b.v);}
inline mod_ullt&operator-=(mod_ullt b){return*this=_chg(v+chg(p-b.v));}
inline mod_ullt&operator*=(mod_ullt b){return*this=v*b.v;}
mod_ullt&operator^=(ullt b){return*this=_power(b);}
mod_ullt&operator/=(mod_ullt b){return*this=b._power(p-2)*v;}
mod_ullt&operator++(){return v=chg(v+1),*this;}
};
}
namespace NTT_POLY
{
template<const ullt p,const ullt g>
class poly_NTT
{
public:
typedef ConstMod::mod_ullt<p>modint;
typedef std::vector<modint>modvec;
private:
modvec V;
public:
class NTT
{
private:
uint n;uint*T;modint*G;
public:
NTT():n(0),T(NULL),G(NULL){}
NTT(uint len)
{
n=1;while(n<len)n<<=1;
T=new uint[n],G=new modint[n],T[0]=0,G[0]=1;
for(uint i=1;i<n;i++)T[i]=((i&1)?n|T[i>>1]:T[i>>1])>>1;
modint w=power(g,(p-1)/n,p),*End=G+n;
for(modint*_G=G+1;_G<End;_G++)*_G=_G[-1]*w;
}
~NTT(){if(T!=NULL)delete[]T,delete[]G,T=NULL,G=NULL;}
inline uint size(){return n;}
voi bzr(uint len)
{
n=1;while(n<len)n<<=1;
if(T!=NULL)delete[]T,delete[]G;
T=new uint[n],G=new modint[n],T[0]=0,G[0]=1;
for(uint i=1;i<n;i++)T[i]=((i&1)?n|T[i>>1]:T[i>>1])>>1;
modint w=power(g,(p-1)/n,p),*End=G+n;
for(modint*_G=G+1;_G<End;_G++)*_G=_G[-1]*w;
}
voi ntt(modvec&x,bol op)
{
if(x.size()<n)x.resize(n);
for(uint i=0;i<n;i++)if(T[i]<i)std::swap(x[i],x[T[i]]);
for(uint i=1;i<n;i<<=1)for(uint j=0;j<n;j+=i<<1)
{
modint*w=G;
for(uint k=0;k<i;k++,w+=n/(2*i))
{
modint t=x[i+j+k]*(*w);
x[i+j+k]=x[j+k]-t,x[j+k]+=t;
}
}
if(op)
{
for(uint i=1;i*2<n;i++)std::swap(x[i],x[n-i]);
modint t=modint(n).inv();for(uint i=0;i<n;i++)x[i]*=t;
}
}
inline modint Omega(uint n){return G[n%size()];}
NTT&operator=(NTT b)
{
if(T!=NULL)delete[]T,delete[]G,T=NULL,G=NULL;
if(b.T==NULL)return*this;
T=new uint[n],G=new modint[n=b.n];
for(uint i=0;i<n;i++)T[i]=b.T[i],G[i]=b.G[i];
return*this;
}
};
class DIFDIT
{
private:
uint n;modint*G;
public:
DIFDIT():n(0),G(NULL){}
DIFDIT(uint len)
{
n=1;while(n<len)n<<=1;
G=new modint[n],G[0]=1;
modint w=power(g,(p-1)/n,p),*End=G+n;
for(modint*_G=G+1;_G<End;_G++)*_G=_G[-1]*w;
}
~DIFDIT(){if(G!=NULL)delete[]G,G=NULL;}
inline uint size(){return n;}
voi bzr(uint len)
{
n=1;while(n<len)n<<=1;
if(G!=NULL)delete[]G;
G=new modint[n],G[0]=1;
modint w=power(g,(p-1)/n,p),*End=G+n;
for(modint*_G=G+1;_G<End;_G++)*_G=_G[-1]*w;
}
voi dif(modvec&x)
{
if(x.size()<n)x.resize(n);
for(uint i=n>>1;i;i>>=1)for(uint j=0;j<n;j+=i<<1)
{
modint*w=G;
for(uint k=0;k<i;k++,w+=n/(2*i))
{
modint u=x[j+k],t=x[i+j+k];
x[j+k]=u+t,x[i+j+k]=(u-t)*(*w);
}
}
}
voi dit(modvec&x)
{
if(x.size()<n)x.resize(n);
for(uint i=1;i<n;i<<=1)for(uint j=0;j<n;j+=i<<1)
{
modint*w=G;
for(uint k=0;k<i;k++,w+=n/(2*i))
{
modint t=x[i+j+k]*(*w);
x[i+j+k]=x[j+k]-t,x[j+k]+=t;
}
}
for(uint i=1;i*2<n;i++)std::swap(x[i],x[n-i]);
modint t=modint(n).inv();for(uint i=0;i<n;i++)x[i]*=t;
}
DIFDIT&operator=(DIFDIT b)
{
if(G!=NULL)delete[]G,G=NULL;
if(b.G==NULL)return*this;
G=new modint[n=b.n];
for(uint i=0;i<n;i++)G[i]=b.G[i];
return*this;
}
};
public:
poly_NTT(){}
poly_NTT(uint n){V.resize(n);}
poly_NTT(modvec V):V(V){}
inline voi bzr(){V.clear();}
inline voi push(modint v){V.push_back(v);}
inline voi pop(){V.pop_back();}
inline voi cut_zero(){while(!V.empty()&&V.back().empty())V.pop_back();}
inline voi chg_siz(uint n){V.resize(n);}
inline voi chg_deg(uint n){V.resize(n+1);}
inline bol empty(){return cut_zero(),V.empty();}
inline uint size(){return V.size();}
inline uint deg(){return V.size()-1;}
inline modint val(uint n){return(n<size())?V[n]:0;}
inline modvec GET(){return V;}
poly_NTT reverse()
{
poly_NTT ans;for(uint i=size()-1;~i;i--)ans.push(V[i]);
return ans;
}
friend poly_NTT operator+(poly_NTT a,poly_NTT b)
{
if(a.size()<b.size())a.chg_siz(b.size());
for(uint i=0;i<b.size();i++)a[i]+=b[i];
a.cut_zero();return a;
}
friend poly_NTT operator+(poly_NTT a,modint v)
{
if(!a.size())a.chg_siz(1);
a[0]+=v;return a;
}
friend poly_NTT operator+(modint v,poly_NTT a)
{
if(!a.size())a.chg_siz(1);
a[0]+=v;return a;
}
friend poly_NTT operator-(poly_NTT a){return a*modint(p-1);}
friend poly_NTT operator-(poly_NTT a,poly_NTT b)
{
if(a.size()<b.size())a.chg_siz(b.size());
for(uint i=0;i<b.size();i++)a[i]-=b[i];
a.cut_zero();return a;
}
friend poly_NTT operator-(poly_NTT a,modint v)
{
if(!a.size())a.chg_siz(1);
a[0]-=v;return a;
}
friend poly_NTT operator-(modint v,poly_NTT a)
{
if(!a.size())a.chg_siz(1);
a[0]-=v;return-a;
}
friend poly_NTT operator*(poly_NTT a,poly_NTT b)
{
modvec&A=a.V,&B=b.V;DIFDIT s(A.size()+B.size());
s.dif(A),s.dif(B);for(uint i=0;i<s.size();i++)A[i]*=B[i];
s.dit(A),a.cut_zero();return a;
}
friend poly_NTT operator*(poly_NTT A,modint b)
{
for(auto&s:A.V)s*=b;
return A;
}
friend poly_NTT operator*(modint b,poly_NTT A)
{
for(auto&s:A.V)s*=b;
return A;
}
friend poly_NTT operator<<(poly_NTT a,uint k)
{
poly_NTT ans;ans.chg_siz(k);for(auto v:a.V)ans.push(v);
return ans;
}
friend poly_NTT operator>>(poly_NTT a,uint k)
{
poly_NTT ans;for(uint i=k;i<a.size();i++)ans.push(a[i]);
return ans;
}
friend poly_NTT sub_mul(poly_NTT a,poly_NTT b)
{
uint len=(a=a.reverse()).size();
modvec&A=a.V,&B=b.V;
DIFDIT s(len+B.size());
s.dif(A),s.dif(B);for(uint i=0;i<s.size();i++)A[i]*=B[i];
s.dit(A),a.chg_siz(len),a=a.reverse();return a;
}
poly_NTT inv(){return inv(size());}
poly_NTT inv(uint prec)
{
modvec ans;DIFDIT s;ans.push_back(V[0].inv());
for(uint tp=1;tp<prec;tp<<=1)
{
modvec f(tp<<1),t=ans;
for(uint i=0;i<(tp<<1);++i)f[i]=val(i);
s.bzr(tp<<1),s.dif(f),s.dif(t);
for(uint i=0;i<(tp<<1);++i)f[i]=1-f[i]*t[i];
s.dit(f);
for(uint i=0;i<tp;++i)f[i]=f[i+tp],f[i+tp]=0;
s.dif(f);
for(uint i=(tp<<1)-1;~i;--i)f[i]*=t[i];
s.dit(f),ans.resize(tp<<1);
for(uint i=0;i<tp;++i)ans[i+tp]=f[i];
}
ans.resize(prec);return ans;
}
poly_NTT sqrt(){return sqrt(size());}
poly_NTT sqrt(uint prec)
{
modvec ans,Inv;ans.push_back(val(0).sqrt()),Inv.push_back(ans[0].inv());
DIFDIT s;
modint w=modint(2).inv();
for(uint tp=1;tp<prec;tp<<=1)
{
s.bzr(tp<<2);
modvec f(tp<<1);for(uint i=0;i<(tp<<1);i++)f[i]=val(i);
s.dif(Inv);s.dif(ans);
for(uint i=0;i<(tp<<2);i++)Inv[i]*=2-Inv[i]*ans[i];
s.dit(Inv),Inv.resize(tp);s.dif(Inv);
for(uint i=0;i<(tp<<2);i++)Inv[i]*=2-Inv[i]*ans[i];
s.dit(Inv),Inv.resize(tp<<1);
modvec user=Inv;s.dif(Inv),s.dif(f);
for(uint i=0;i<(tp<<2);i++)ans[i]=(ans[i]+Inv[i]*f[i])*w;
s.dit(ans),Inv=user,ans.resize(tp<<1);
}
ans.resize(prec);return ans;
}
poly_NTT diff()
{
poly_NTT ans;for(uint i=1;i<size();i++)ans.push(i*V[i]);
return ans;
}
poly_NTT inte()
{
if(!size())return*this;
poly_NTT ans(size()+1);ans[1]=1;
for(uint i=2;i<=size();i++)ans[i]=-ans[p%i]*(p/i);
for(uint i=1;i<=size();i++)ans[i]*=V[i-1];
return ans;
}
poly_NTT ln(){return ln(size());}
poly_NTT ln(uint prec)
{
poly_NTT a=this->diff()*this->inv(prec);a.chg_siz(prec),a=a.inte(),a.chg_siz(prec);return a;
}
poly_NTT exp(){return exp(size());}
poly_NTT exp(uint prec)
{
poly_NTT ans;modvec Inv;ans.push(1),Inv.push_back(1);
for(uint tp=1;tp<prec;tp<<=1)
{
modvec f,ff=ans.diff().V;
for(uint i=0;i<(tp<<1);i++)f.push_back(val(i));
f[0]=1;DIFDIT s(tp<<2);s.dif(ans.V),s.dif(Inv);
for(uint i=0;i<(tp<<2);i++)Inv[i]*=2-Inv[i]*ans[i];
s.dit(Inv),Inv.resize(tp);s.dif(Inv);
for(uint i=0;i<(tp<<2);i++)Inv[i]*=2-Inv[i]*ans[i];
s.dit(Inv),Inv.resize(tp<<1);s.dif(Inv);s.dif(ff);
for(uint i=0;i<(tp<<2);i++)ff[i]*=Inv[i];
s.dit(ff);f=(f-poly_NTT(ff).inte()).V;s.dif(f);
for(uint i=0;i<(tp<<2);i++)ans[i]*=f[i];
s.dit(Inv),s.dit(ans.V),ans.chg_siz(tp<<1);
}
ans.chg_siz(prec);return ans;
}
friend poly_NTT operator/(poly_NTT a,poly_NTT b)
{
a.cut_zero(),b.cut_zero();if(a.size()<b.size())return poly_NTT();
poly_NTT ans=a.reverse()*b.reverse().inv(a.size()-b.size()+1);
ans.chg_siz(a.size()-b.size()+1);return ans.reverse();
}
friend poly_NTT operator%(poly_NTT a,poly_NTT b){return a-a/b*b;}
public:
inline modint&operator[](uint n){return V[n];};
poly_NTT&operator+=(poly_NTT b)
{
if(size()<b.size())chg_siz(b.size());
for(uint i=0;i<b.size();i++)V[i]+=b[i];
cut_zero();return*this;
}
inline poly_NTT&operator+=(modint v)
{
if(!size())chg_siz(1);
V[0]+=v;return*this;
}
poly_NTT&operator-=(poly_NTT b)
{
if(size()<b.size())chg_siz(b.size());
for(uint i=0;i<b.size();i++)V[i]-=b[i];
cut_zero();return*this;
}
inline poly_NTT&operator-=(modint v)
{
if(!size())chg_siz(1);
V[0]-=v;return*this;
}
poly_NTT&operator*=(poly_NTT b)
{
modvec&A=V,&B=b.V;
DIFDIT s(A.size()+B.size());
s.dif(A),s.dif(B);
for(uint i=0;i<s.size();i++)A[i]*=B[i];
s.dit(A),cut_zero();return*this;
}
poly_NTT&operator*=(modint v)
{
for(auto&t:V)t*=v;
return*this;
}
poly_NTT&operator/=(poly_NTT b){return*this=*this/b;}
poly_NTT&operator%=(poly_NTT b){return*this=*this%b;}
poly_NTT&operator<<=(uint v){return*this=*this<<v;}
poly_NTT&operator>>=(uint v){return*this=*this>>v;}
};
template<const ullt p,const ullt g>
class poly_eval
{
public:
typedef ConstMod::mod_ullt<p>modint;
typedef std::vector<modint>modvec;
typedef poly_NTT<p,g>poly;
private:
std::vector<poly>G,User;modvec X;
voi mult_eval_dfs1(uint u,uint l,uint r)
{
if(l+1==r){G[u].push(1),G[u].push(-X[l]);return;}
uint mid=(l+r)/2;mult_eval_dfs1(u<<1,l,mid),mult_eval_dfs1(u<<1|1,mid,r),G[u]=G[u<<1]*G[u<<1|1];
}
voi mult_eval_dfs2(uint u,uint l,uint r)
{
User.back().chg_siz(r-l);
if(l+1==r){X[l]=User.back().val(0);return;}
uint mid=(l+r)/2;
User.push_back(sub_mul(User.back(),G[u<<1|1])),mult_eval_dfs2(u<<1,l,mid);
User.back()=sub_mul(User[User.size()-2],G[u<<1]),mult_eval_dfs2(u<<1|1,mid,r);
User.pop_back();
}
public:
voi operator()(poly P,modvec&X)
{
if(X.empty())return;
G.resize(X.size()<<2),User.clear(),this->X=X;
mult_eval_dfs1(1,0,X.size());
User.push_back(sub_mul(P,G[1].inv(std::max<uint>(P.size(),X.size())+1)));
mult_eval_dfs2(1,0,X.size());
G.clear(),User.clear(),X=this->X,this->X.clear();
}
};
template<const ullt p,const ullt g>
class poly_inter
{
public:
typedef ConstMod::mod_ullt<p>modint;
typedef std::vector<modint>modvec;
typedef poly_NTT<p,g>poly;
typedef poly_eval<p,g>eval;
private:
std::vector<poly>Lim,F,G;modvec X,H;
voi dfs(uint l,uint r)
{
if(l+1==r)
{
F.push_back(poly()),F.back().push(H[l]),G.push_back(poly()),G.back().push(-X[l]),G.back().push(1);return;
}
uint mid=(l+r)>>1;dfs(l,mid),dfs(mid,r);
F[F.size()-2]=F[F.size()-2]*G.back()+F.back()*G[G.size()-2],F.pop_back(),G[G.size()-2]*=G.back(),G.pop_back();
}
public:
poly operator()(modvec X,modvec Y)
{
uint n=std::min(X.size(),Y.size());if(!n)return poly();
X.resize(n),Y.resize(n),this->X=X;poly P;Lim.clear();
for(uint i=0;i<n;i++)
{
P.bzr(),P.push(-X[i]),P.push(1);
uint w=lowbit(i+1);while(w>>=1)P*=Lim.back(),Lim.pop_back();
Lim.push_back(P);
}
P=Lim.back(),Lim.pop_back();while(Lim.size())P*=Lim.back(),Lim.pop_back();
eval()(P.diff(),X),H.resize(n);for(uint i=0;i<n;i++)H[i]=Y[i]/X[i];
F.clear(),G.clear(),dfs(0,n);
poly ans=F.back();F.clear(),G.clear(),this->X.clear(),H.clear();return ans;
}
};
template<const ullt p,const ullt g>
class poly_cpd
{
public:
typedef ConstMod::mod_ullt<p>modint;
typedef std::vector<modint>modvec;
typedef poly_NTT<p,g>poly;
modvec Turn(std::vector<llt>QAQ)
{
modvec ans;
for(uint i=0;i<QAQ.size();i++)ans.push_back((QAQ[i]%(llt)p+p)%p);
return ans;
}
modint point_eval(poly P,modint x)
{
modint ans;
for(uint i=P.deg();~i;i--)ans=ans*x+P[i];
return ans;
}
poly z_npow(poly P,uint n)
{
if(P.empty())return P;
poly ans(P.deg()*n+1);
for(uint i=0;i<P.size();i++)ans[i*n]+=P[i];
return ans;
}
poly z_npow(poly P,uint n,uint prec)
{
poly ans(prec);
for(uint i=0;i<P.size()&&i*n<prec;i++)ans[i*n]+=P[i];
return ans;
}
poly z_mul_k(poly P,modint k)
{
modint t(1);
for(uint i=0;i<P.size();i++)P[i]*=t,t*=k;
return P;
}
poly z_add_v(poly P,modint v)
{
uint n=P.size();if(!n)return P;
modvec A(n),B(n);
A[0]=1;for(uint i=1;i<n;i++)A[i]=A[i-1]*i;
B[n-1]=A[n-1].inv();for(uint i=n-1;i;i--)B[i-1]=B[i]*i;
poly User(n);modint w(1);
for(uint i=0;i<n;i++)P[i]*=A[i],User[i]=w*B[i],w*=v;
P=sub_mul(P,User),P.chg_siz(n);
for(uint i=0;i<n;i++)P[i]*=B[i];
return P;
}
poly chg_siz(poly P,uint siz){P.chg_siz(siz);return P;}
poly PolyaInv(poly P,uint prec){return(modint(1)-P).inv(prec);}
poly PolyaExp(poly P,uint prec)
{
modvec inv(prec);
inv[1]=1;for(uint i=2;i<prec;i++)inv[i]=(p/i)*-inv[p%i];
poly ans(prec);
for(uint i=1;i<prec;i++)for(uint j=1;i*j<prec&&j<P.size();j++)ans[i*j]+=P[j]*inv[i];
return ans.exp(prec);
}
poly PolyaInv(poly P){return PolyaInv(P,P.size());}
poly PolyaExp(poly P){return PolyaExp(P,P.size());}
voi println(poly P,uint n)
{
for(uint i=0;i<n;i++){
if(i)putchar(' ');
P.val(i).print();
}
putchar('\n');
}
voi println(poly P){println(P,P.size());}
};
template<const ullt p,const ullt g>
class poly_nums
{
public:
typedef ConstMod::mod_ullt<p>modint;
typedef std::vector<modint>modvec;
typedef poly_NTT<p,g>poly;
typedef poly_cpd<p,g>cpd;
modvec PowSum(uint n,uint m)
{
modvec P(n+2),Q(n+2);
P[0]=1;for(uint i=1;i<=n+1;i++)P[i]=P[i-1]*i;
Q[n+1]=P[n+1].inv();for(uint i=n+1;i;i--)Q[i-1]=Q[i]*i;
poly A(n+1);for(uint i=0;i<=n;i++)A[i]=Q[i+1];
A=A.inv();
poly B(n+1);modint v(1);for(uint i=0;i<=n;i++)B[i]=v*Q[i],v*=m;
B=(B*A-A)>>1;B.chg_siz(n);
for(uint i=0;i<n;i++)B[i]*=P[i];
return B.GET();
}
modvec S1R(uint n)
{
if(!n)return modvec({modint(1)});
if(n&1)return(S1R(n-1)*poly(modvec({n-1,1}))).GET();
poly P=S1R(n>>1);P*=cpd().z_add_v(P,n>>1);return P.GET();
}
modvec S1C(uint n,uint prec)
{
if(n>=prec)return modvec(prec);
modvec P(prec+1),Q(prec+1);
P[0]=1;for(uint i=1;i<=prec;i++)P[i]=P[i-1]*i;
Q[prec]=P[prec].inv();for(uint i=prec;i;i--)Q[i-1]=Q[i]*i;
poly ans;
for(uint i=1;i<=prec-n;i++)ans.push(Q[i]*P[i-1]);
ans=(ans.ln(prec-n)*modint(n)).exp(prec-n)<<n;
modint v=1;
for(uint i=1;i<=n;i++)v*=i;
ans=ans*v.inv();
for(uint i=n;i<prec;i++)ans[i]*=P[i];
return ans.GET();
}
modvec S2R(uint n)
{
modvec P(n+1),Q(n+1);
P[0]=1;for(uint i=1;i<=n;i++)P[i]=P[i-1]*i;
Q[n]=P[n].inv();for(uint i=n;i;i--)Q[i-1]=Q[i]*i;
poly A(n+1),B(n+1);
A[0]=!n;if(n)A[1]=1;
std::vector<uint>Prime;
std::vector<bol>Gone(n+1);
for(uint i=2;i<=n;i++)
{
if(!Gone[i]){Prime.push_back(i);modint v=modint(i)._power(n);for(ullt j=i;j<=n;j*=i)A[j]=v*A[j/i],Gone[j]=true;}
for(auto w:Prime)if(i*w<=n&&i%w){for(ullt j=w;i*j<=n;j*=w)A[i*j]=A[i]*A[j],Gone[i*j]=true;}else break;
}
for(uint i=0;i<=n;i++)A[i]*=Q[i],B[i]=(i&1?p-1:1)*Q[i];
A*=B,A.chg_deg(n);
return A.GET();
}
modvec S2C(uint n,uint prec)
{
if(n>=prec)return modvec(prec);
modvec P(prec+1),Q(prec+1);
P[0]=1;for(uint i=1;i<=prec;i++)P[i]=P[i-1]*i;
Q[prec]=P[prec].inv();for(uint i=prec;i;i--)Q[i-1]=Q[i]*i;
poly ans=PowSum(prec-n,n+1);
ans[0]=0;for(uint i=1;i<prec-n;i++)ans[i]*=Q[i]*P[i-1];
ans=ans.exp(prec-n)<<n;
return ans.GET();
}
};
}
namespace FWT_MODINT
{
template<const ullt p>
class FWT_Mod
{
public:
typedef ConstMod::mod_ullt<p>modint;
typedef std::vector<modint>modvec;
private:
uint n;
public:
FWT_Mod():n(0){}
voi bzr(uint len){n=1;while(n<len)n<<=1;}
uint size(){return n;}
voi OR(modvec&x,bol op)
{
if(x.size()<n)x.resize(n);
for(uint i=1;i<n;i<<=1)for(uint j=0;j<n;j+=i<<1)for(uint k=0;k<i;k++)
op?x[i+j+k]-=x[j+k]:x[i+j+k]+=x[j+k];
}
voi AND(modvec&x,bol op)
{
if(x.size()<n)x.resize(n);
for(uint i=1;i<n;i<<=1)for(uint j=0;j<n;j+=i<<1)for(uint k=0;k<i;k++)
op?x[j+k]-=x[i+j+k]:x[j+k]+=x[i+j+k];
}
voi XOR(modvec&x,bol op)
{
if(x.size()<n)x.resize(n);
for(uint i=1;i<n;i<<=1)for(uint j=0;j<n;j+=i<<1)for(uint k=0;k<i;k++)
{
modint u=x[j+k],t=x[i+j+k];x[j+k]=u+t,x[i+j+k]=u-t;
}
if(op){modint v=modint(n).inv();for(uint i=0;i<n;i++)x[i]*=v;}
}
};
}
const ullt Mod=998244353,g=3;
typedef ConstMod::mod_ullt<Mod>modint;
typedef std::vector<modint>modvec;
typedef NTT_POLY::poly_NTT<Mod,g>poly;
typedef NTT_POLY::poly_eval<Mod,g>eval;
typedef NTT_POLY::poly_inter<Mod,g>inter;
typedef NTT_POLY::poly_cpd<Mod,g>cpd;
typedef NTT_POLY::poly_nums<Mod,g>nums;
typedef FWT_MODINT::FWT_Mod<Mod>FWT;
uint Cnt[2000005],Min[2000005];
std::vector<uint>CntP[2000005];uint NowTp[2000005];
modint Inv[2000005],LCM(1);
voi insert(uint v){
while(v>1){
uint s=Min[v],w=0;while(Min[v]==s)w++,v/=s;
CntP[s][w]++;while(NowTp[s]<w)LCM*=s,NowTp[s]++;
}
}
voi erase(uint v){
while(v>1){
uint s=Min[v],w=0;while(Min[v]==s)w++,v/=s;
CntP[s][w]--;while(!CntP[s][NowTp[s]])LCM*=Inv[s],NowTp[s]--;
}
}
int main()
{
#ifdef MYEE
freopen("QAQ.in","r",stdin);
// freopen("QAQ.out","w",stdout);
#endif
for(uint i=2;i<=2000000;i++){
static std::vector<uint>Prime;
if(!Min[i]){
Prime.push_back(i);
uint c=0;for(ullt t=i;t<=2000000;t*=i)c++,Min[t]=i;
CntP[i].resize(c+1),CntP[i][0]=1;
}
for(auto s:Prime)if(i%s&&i*s<=2000000){
for(ullt t=s;i*t<=2000000;t*=s)Min[i*t]=s;
}else break;
}
for(uint i=1;i<=2000000;i++)Inv[i]=modint(i).inv();
uint n;scanf("%u",&n);modint ans;
for(uint i=0,v;i<n;i++)scanf("%u",&v),Cnt[v]++,insert(v);
poly P(1000001),Q;
for(uint i=1;i<=1000000;i++)
if(Cnt[i]>1)P[i]=Cnt[i];
else if(Cnt[i]==1){modint v=LCM;erase(i);v=LCM/v,insert(i),P[i]=v;}
Q=P*P;
for(uint i=1;i<=1000000;i++)if(Cnt[i]>1)Q[i*2]-=Cnt[i];else if(Cnt[i]==1)Q[i*2]-=P[i]*P[i];
Q*=modint(2).inv();
for(uint i=1;i<=2000000;i++)if(Q.val(i)())insert(i),ans+=Q.val(i)*LCM,erase(i);
ans.println();
return 0;
}
// 那就是希望。
// 即便需要取模,也是光明。
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 963ms
memory: 150820kb
input:
96709 888451 516254 906133 347209 680059 352562 559092 51645 805639 208345 690286 512761 405948 902987 481307 401690 964462 704714 771809 946054 331027 715301 899161 905069 871833 223641 661393 773039 703447 949204 590357 952617 532852 801806 896897 974849 595373 648200 784789 740171 522959 946981 9...
output:
317859717
result:
ok single line: '317859717'
Test #2:
score: 0
Accepted
time: 969ms
memory: 148972kb
input:
500000 132179 56907 160114 921536 921536 160114 921536 56907 26017 132179 26017 590365 56907 132179 56907 160114 160114 377247 377247 160114 160114 91200 56907 921536 91200 590365 160114 504174 377247 56907 132179 91200 132179 132179 91200 590365 160114 91200 377247 30631 56907 26017 26017 91200 921...
output:
853619659
result:
ok single line: '853619659'
Test #3:
score: 0
Accepted
time: 908ms
memory: 148996kb
input:
4883 347062 234948 766629 954124 305767 18582 224896 461186 148474 86197 698808 413499 286357 806937 297603 735016 557034 636363 185180 940722 190964 808094 241391 283851 581235 660421 875791 550632 804950 834718 126518 389136 231188 227150 959147 762772 19367 939679 933098 150368 233339 956109 1808...
output:
385014000
result:
ok single line: '385014000'
Test #4:
score: 0
Accepted
time: 946ms
memory: 151364kb
input:
27943 217360 702214 253520 779644 556142 556300 386035 757853 984695 864620 619819 13084 664068 973066 174047 873958 726742 653890 781777 411151 703033 301904 58419 159086 700216 896124 871138 302148 125900 351930 462287 173720 269649 186418 304361 286120 958557 411911 18242 744958 409144 677486 143...
output:
214762986
result:
ok single line: '214762986'
Test #5:
score: 0
Accepted
time: 987ms
memory: 151560kb
input:
186170 310454 97457 958948 823456 848927 176202 899032 488541 373103 770802 335003 362174 693540 851736 752536 830917 501120 553219 337883 839564 394144 538498 580666 90035 932191 272143 449733 663693 993744 474097 595691 58896 170220 477669 936225 836223 855254 620546 992377 545362 46370 163908 836...
output:
75077307
result:
ok single line: '75077307'
Test #6:
score: 0
Accepted
time: 1113ms
memory: 151332kb
input:
461635 597343 754468 767171 132818 668074 941520 687283 259355 434890 187925 960388 573728 677884 252358 526652 656422 709003 194958 96004 556213 506136 530473 242932 105452 365342 742732 946199 158101 771855 733211 510859 644771 549744 56792 393492 274640 291094 870555 31498 866856 865391 117602 11...
output:
937091194
result:
ok single line: '937091194'
Test #7:
score: 0
Accepted
time: 1043ms
memory: 150820kb
input:
194282 700822 989293 924557 450818 445936 129331 932692 788512 320143 46127 609422 750817 616292 816791 62263 744286 16679 206183 66146 98782 775153 436169 654046 957959 886852 217001 471907 619813 565904 492511 674957 868307 466649 648997 309362 229499 787333 23294 633781 288653 297524 964282 76786...
output:
917619265
result:
ok single line: '917619265'
Test #8:
score: 0
Accepted
time: 1033ms
memory: 152820kb
input:
274937 421277 600214 66886 548046 173912 983674 641240 13191 543328 712058 237791 155490 972292 153487 740371 812220 392383 396000 94351 189262 643305 655496 137184 117514 499669 842950 109626 57125 717207 89407 606654 182960 270097 590141 605770 14170 883600 395413 662376 911163 344273 667507 87414...
output:
216164675
result:
ok single line: '216164675'
Test #9:
score: 0
Accepted
time: 1101ms
memory: 150980kb
input:
383978 851871 877586 361600 786208 526058 465064 368789 2497 421862 354594 130900 493744 828354 703585 806951 138487 440549 990454 35846 927839 798279 257958 591659 214523 999499 896942 230281 777473 757874 569698 49428 587726 771296 549685 675264 716837 690729 445449 544004 623061 549322 357348 590...
output:
407714524
result:
ok single line: '407714524'
Test #10:
score: 0
Accepted
time: 1070ms
memory: 152288kb
input:
455853 597761 696372 83500 686162 392679 939871 431141 848570 438287 223903 47070 847771 754034 477428 971806 989734 118635 84249 230083 701866 169021 352675 706546 954030 934478 52915 429165 315039 457715 872533 672806 768061 197745 622182 885533 999945 799179 672700 83573 778177 185958 389570 3607...
output:
721056673
result:
ok single line: '721056673'