QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #66595 | #5169. 夹娃娃 | myee | 3 | 1321ms | 2988kb | C++14 | 29.5kb | 2022-12-09 09:26:27 | 2022-12-09 09:26:29 |
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;
const uint M=520;
poly P[25];
chr C[25];
poly mul(poly a,poly b,uint m){
poly ans=a*b;
if(ans.size()>m)ans.chg_deg(m),ans.cut_zero();
return ans;
}
int main()
{
#ifdef MYEE
freopen("QAQ.in","r",stdin);
// freopen("QAQ.out","w",stdout);
#else
#if !defined(ONLINE_JUDGE)
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
#endif
uint n,q;scanf("%u%u%*u",&n,&q);
for(uint i=0;i<n;i++){
P[i]=modvec{1},P[i].chg_deg(M);
uint t;scanf("%u",&t);
while(t--){
uint b,c;scanf("%u%u",&b,&c);c=(c+1)*b;
for(uint j=b;j<=M;j++)P[i][j]+=P[i][j-b];
for(uint j=M;j>=c;j--)P[i][j]-=P[i][j-c];
}
P[i].cut_zero();
}
while(q--){
uint m,k;scanf("%s%u%u",C,&m,&k);
poly ans=modvec{1};
for(uint j=0;j<n;j++)
{
poly T=P[j];
if(C[j]=='1'){
if(T.size()>k)for(uint p=0;p<k;p++)T[p]=0;
else T=modvec{};
}
ans=mul(T,ans,m);
}
cpd().point_eval(ans,1).println();
}
return 0;
}
// 那就是希望。
// 即便需要取模，也是光明。
详细
Subtask #1:
score: 3
Accepted
Test #1:
score: 3
Accepted
time: 34ms
memory: 2920kb
input:
1 521 998244353 39 520 520 11 22 414 8 95 18 229 356 26 407 316 10 24 26 19 61 11 130 482 476 420 15 192 193 208 24 19 233 494 217 275 294 26 28 439 20 272 277 28 198 5 335 22 8 28 17 154 78 6 13 175 17 2 5 477 256 200 4 1 36 427 371 439 23 10 65 426 25 24 27 121 29 28 13 12 453 0 520 1 1 519 1 1 51...
output:
38813347 922143638 98254957 38813343 922143633 38813338 98254946 922143620 98254933 922143604 38813302 38813288 922143562 38813247 38813220 38813188 38813150 98254715 38813047 922143273 98254516 38812814 922142999 98254191 922142723 38812257 38812058 98253436 922141847 38811240 922141173 38810463 38...
result:
ok 521 lines
Test #2:
score: 0
Accepted
time: 298ms
memory: 2952kb
input:
2 1561 998244353 151 520 520 511 30 121 396 25 16 113 11 6 175 242 20 8 5 61 13 518 447 404 8 220 177 4 19 18 15 70 233 9 14 26 512 17 9 9 19 30 8 495 20 13 27 277 22 396 14 4 29 345 442 19 25 14 5 16 295 19 65 134 10 10 296 245 6 7 30 253 15 187 26 482 454 28 414 170 404 11 27 27 25 13 509 1 5 291 ...
output:
883965618 144348435 762074635 112296779 385763651 821718611 673974966 879750066 927942969 136450507 436584627 612945970 768262217 613885343 39304132 852224740 215596261 151746110 965953558 969833936 664053020 458247365 881060255 878484499 781573019 616944059 850325449 296113117 674829177 887392623 6...
result:
ok 1561 lines
Subtask #2:
score: 0
Time Limit Exceeded
Dependency #1:
100%
Accepted
Test #3:
score: 13
Accepted
time: 1321ms
memory: 2988kb
input:
3 4160 998244353 444 520 520 26 332 29 183 25 479 175 14 13 16 1 447 2 293 4 20 64 472 491 11 21 259 75 22 390 401 8 508 405 3 137 4 15 154 164 1 484 13 257 14 44 20 7 13 26 15 26 432 14 9 478 24 18 10 22 28 8 21 260 25 431 22 7 6 20 26 8 27 239 19 1 134 2 322 16 225 6 42 517 6 197 407 268 500 433 5...
output:
516056999 990096150 497048298 345860798 899328070 577475723 191997503 533625761 516056999 863614705 652318084 514747110 811600228 92531482 136793394 218097588 352553395 821305819 739754364 569418540 402235631 844207347 78271439 896568337 516056999 243958673 201200148 634787992 552693501 893938722 98...
result:
ok 4160 lines
Test #4:
score: -13
Time Limit Exceeded
input:
4 8320 998244353 303 520 520 288 10 15 24 306 456 495 124 20 419 24 473 7 462 365 405 4 30 1 29 15 25 29 324 407 14 30 184 425 451 6 414 7 417 155 12 18 20 2 475 78 174 467 23 300 26 13 15 345 319 10 27 497 25 21 51 24 485 359 268 87 20 509 13 18 261 13 6 20 237 305 26 245 330 514 29 21 197 25 345 1...
output:
857239630 694514392 340827658 834331936 573150389 560202020 302111919 422193966 147386541 201821565 447255018 322990367 192787601 197802108 461775999 315804262 316164169 338416167 240429979 359914423 321666890 541700460 506123940 701447430 823947537 621301718 62107305 163486246 380210777 211911024 9...
result:
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Time Limit Exceeded
Test #9:
score: 0
Time Limit Exceeded
input:
15 52099 998244353 1 9 3 1 9 4 1 9 2 1 8 10 1 4 4 1 3 1 1 2 5 1 4 9 1 1 4 1 9 4 1 7 6 1 1 6 1 2 5 1 5 2 1 3 5 101000000001010 516 1 010001001010101 520 2 000000101000001 519 2 101011111100011 518 1 010110001000111 520 2 000110111100111 516 1 000100101001011 519 3 000111001010011 518 1 00001110010111...
output:
993379058 496689529 866368587 797687294 481245176 481245176 39022588 269889529 552778235 769822588 331666941 99789529 903956470 112750588 756797435 519045176 870912000 361582588 594280447 494747647 597778941 178845176 435456000 493445999 461733882 308912117 271186941 496689529 919511294 85533882 894...
result:
Subtask #5:
score: 0
Skipped
Dependency #3:
0%
Subtask #6:
score: 0
Skipped
Dependency #4:
0%
Subtask #7:
score: 0
Skipped
Dependency #6:
0%