用 OGF 表示 (F(B,x)) 就是
[prod_{i=1}^n(1+(q-a_i)x)
]
直接分治 NTT 把 ([x^k]) 也就是这一位的系数求出来就可以了。
至于相互独立的询问直接暴力修改即可。
代码
#define rr register
#define mem(f,n) memset(f,0,sizeof(int)*(n))
#define cpy(f,g,n) memcpy(f,g,sizeof(int)*(n))
using namespace std;
const int mod=998244353,inv3=332748118,N=20011;
typedef long long lll; typedef unsigned long long ull;
inline signed address(){
for (rr int i=0;i<15;++i)
if (!v[i]) return i;
return -1;
}
namespace Theoretic{
int rev[N<<2],LAST; ull Wt[N<<2],F[N<<2];
inline void Pro(int n){
if (LAST==n) return; LAST=n,Wt[0]=1;
for (rr int i=0;i<n;++i)
rev[i]=(rev[i>>1]>>1)|((i&1)?n>>1:0);
}
inline void NTT(int *f,int n,int op){
Pro(n);
for (rr int i=0;i<n;++i) F[i]=f[rev[i]];
for (rr int o=1,len=1;len<n;++o,len<<=1){
rr int W=(op==1)?Gmi[o]:Imi[o];
for (rr int j=1;j<len;++j) Wt[j]=Wt[j-1]*W%mod;
for (rr int i=0;i<n;i+=len+len)
for (rr int j=0;j<len;++j){
rr int t=Wt[j]*F[i|j|len]%mod;
F[i|j|len]=F[i|j]+mod-t,F[i|j]+=t;
}
if (o==10) for (rr int j=0;j<n;++j) F[j]%=mod;
}
if (op==-1){
rr int invn=ksm(n,mod-2);
for (rr int i=0;i<n;++i) F[i]=F[i]%mod*invn%mod;
}else for (rr int i=0;i<n;++i) F[i]%=mod;
for (rr int i=0;i<n;++i) f[i]=F[i];
}
inline void Cb(int *f,int *g,int n){
for (rr int i=0;i<n;++i) f[i]=1ll*f[i]*g[i]%mod;
}
inline signed CDQ_NTT(int x,int l,int r){
if (l==r){
rr int now=address();
len[now]=2,v[now]=ff[now][0]=1,
ff[now][1]=x<a[l]?x-a[l]+mod:x-a[l];
return now;
}
rr int mid=(l+r)>>1,L;
rr int lef=CDQ_NTT(x,l,mid),rig=CDQ_NTT(x,mid+1,r);
for (L=1;L<len[lef]+len[rig];L<<=1);
NTT(ff[lef],L,1),NTT(ff[rig],L,1),Cb(ff[lef],ff[rig],L),
mem(ff[rig],L),len[lef]+=len[rig],len[rig]=v[rig]=0,NTT(ff[lef],L,-1);
return lef;
}
}
inline void GmiImi(){
for (rr int i=0;i<31;++i) Gmi[i]=ksm(3,(mod-1)/(1<<i));
for (rr int i=0;i<31;++i) Imi[i]=ksm(inv3,(mod-1)/(1<<i));
}
signed main(){
n=iut(),m=iut(),GmiImi();
for (rr int i=1;i<=n;++i) a[i]=iut();
for (rr int Q=iut();Q;--Q){
rr int opt=iut(),d=iut(),now;
if (opt==1){
rr int x=iut(),y=iut(),t=a[x];
a[x]=y,now=Theoretic::CDQ_NTT(d,1,n),a[x]=t;
}else{
rr int l=iut(),r=iut(),x=iut();
for (rr int i=l;i<=r;++i) a[i]=a[i]+x>=mod?a[i]+x-mod:a[i]+x;
now=Theoretic::CDQ_NTT(d,1,n);
for (rr int i=l;i<=r;++i) a[i]=a[i]<x?a[i]-x+mod:a[i]-x;
}
print(ff[now][m]),putchar(10);
mem(ff[now],len[now]),len[now]=v[now]=0;
}
return 0;
}