【题解】牛客挑战赛31
A 妈妈的考试
长度为 的序列 ,其中 ,令 ,,你需要求出所有 种情况中,满足 的最小的 和满足 的最大的 。
首先先证一下 和 奇偶性相同:
不妨令所有 都为 ,那么此时的 ,任意一个 变为 都会使 减小 ,而减去一个偶数,奇偶性不变,故 和 奇偶性相同。
所以我们之后求出的每个答案的合法的前提是 且 与 的奇偶性相同。
然后开始推式子。
将 代入,得 ,故有 。
可以发现 和 是形如 的函数关系,于是接下来就好办了。(这里建议读者先把这个函数大致的画出来,便于理解后面的内容)
求满足 的最小的
答案肯定会在零点附近取到,而 ,故只需枚举 这三个位置附近合法的 并更新答案即可。
求满足 的最大的 。
对原函数求导,得 ,观察图像可得 的时候为极大值点,枚举其附近合法的 并更新答案即可。
代码:
#include<bits/stdc++.h> using namespace std; #define ri int #define DEBUG(k...) fprintf(stderr,k) typedef __int128 ll; template<class T>inline bool ckmax(T &x,const T &y){return x<y?x=y,true:false;} template<class T>inline bool ckmin(T &x,const T &y){return x>y?x=y,true:false;} template<class T>inline void clear(T *arr,int siz,int val=0){memset(arr,val,sizeof(T)*(siz+1));} const int maxn=2e5+10; static char pbuf[1000000],*p1=pbuf,*p2=pbuf,obuf[1000000],*o=obuf; #define getchar() p1==p2&&(p2=(p1=pbuf)+fread(pbuf,1,1000000,stdin),p1==p2)?EOF:*p1++ #define putchar(x) (o-obuf<1000000)?(*o++=(x)):(fwrite(obuf,o-obuf,1,stdout),o=obuf,*o++=(x)) inline ll qr(){ ll in=0;register char ch; while(!isdigit(ch=getchar())); do in=(in<<1)+(in<<3)+(ch^48);while(isdigit(ch=getchar())); return in; } template<class T> void qw(T out){ if(out>9)qw(out/10); putchar(out%10|48); } struct flusher{~flusher(){fwrite(obuf,o-obuf,1,stdout);}}autoflush; ll d,k,n; int t_case; inline ll my_sqrt(ll x,ll ex){ ll l=0,r=x,ret=-1; while(l<=r){ ll mid=(l+r)>>1; if(mid*mid*ex<=x)ret=mid,l=mid+1; else r=mid-1; } return ret; } inline bool check(ll x){return x>=-n&&x<=n&&(x&1)==(n&1);} inline ll calc(ll x){return x*(x*x-k);} int main(){ t_case=qr(); while(t_case--){ n=qr(),k=3*n-2,d=my_sqrt(k,1); ll ans1=1e36,ans2=0; for(ll i:{-d,(ll)0,d}) for(ll j=i-2;j<=i+2;++j) if(check(j)&&calc(j)>0) ckmin(ans1,calc(j)); d=my_sqrt(k,3); for(ll i=-d-2;i<=-d+2;++i) if(check(i)) ckmax(ans2,calc(i)); qw(ans1/6),putchar(32),qw(ans2/6),putchar(10); } return 0; }
B 克洛涅的多项式
给出一个 次多项式 以及 个数 ,有一个 次项系数为 的 次多项式 对于所有的 均满足 。给定一个正整数 ,求 的值。
令 ,则有 且 为一个 次多项式,故 的零点式为 ,则 。
代码:
#include<bits/stdc++.h> using namespace std; #define ri int typedef long long ll; const int maxn=1e5+10,mod=998244353; template<class T>inline bool ckmin(T &x,const T &y){return x>y?x=y,1:0;} template<class T>inline bool ckmax(T &x,const T &y){return x<y?x=y,1:0;} template<class T>inline void clear(T *arr,int siz,int val=0){memset(arr,val,sizeof(T)*(siz+1));} static char pbuf[1000000],*p1=pbuf,*p2=pbuf; #define getchar() p1==p2&&(p2=(p1=pbuf)+fread(pbuf,1,1000000,stdin),p1==p2)?EOF:*p1++ inline int qr(){ ri in=0;char ch; while(!isdigit(ch=getchar())); do in=(in<<1)+(in<<3)+(ch^48);while(isdigit(ch=getchar())); return in; } struct modint{ int val; inline modint(int val_=0):val(val_){} inline modint &operator=(int val_){return val=val_,*this;} inline modint &operator+=(const modint &k){return val=val+k.val>=mod?val+k.val-mod:val+k.val,*this;} inline modint &operator-=(const modint &k){return val=val-k.val<0?val-k.val+mod:val-k.val,*this;} inline modint &operator*=(const modint &k){return val=1ll*val*k.val%mod,*this;} inline modint &operator^=(int k){ modint ret=1,tmp=*this; for(;k;k>>=1,tmp*=tmp)if(k&1)ret*=tmp; return val=ret.val,*this; } inline modint &operator/=(modint k){return *this*=(k^=mod-2);} inline modint &operator+=(int k){return val=val+k>=mod?val+k-mod:val+k,*this;} inline modint &operator-=(int k){return val=val<k?val-k+mod:val-k,*this;} inline modint &operator*=(int k){return val=1ll*val*k%mod,*this;} inline modint &operator/=(int k){return *this*=((modint(k))^=mod-2);} template<class T>friend modint operator+(modint a,T b){return a+=b;} template<class T>friend modint operator-(modint a,T b){return a-=b;} template<class T>friend modint operator*(modint a,T b){return a*=b;} template<class T>friend modint operator^(modint a,T b){return a/=b;} template<class T>friend modint operator/(modint a,T b){return a/=b;} friend modint operator^(modint a,int b){return a^=b;} friend bool operator==(modint a,int b){return a.val==b;} friend bool operator!=(modint a,int b){return a.val!=b;} inline bool operator!(){return !val;} inline modint operator-(){return val?mod-val:0;} inline modint &operator++(){return *this+=1;} }; using mi=modint; mi ans=1,k,kk=1; int m,n; int main(){ // F(x)-G(x)=H(x) // x in S, H(x)=0 // F(x)=G(x)+H(x) n=qr(),m=qr()+1,k=qr(); while(n--)ans*=(k-qr()); while(m--)ans+=kk*qr(),kk*=k; printf("%d",ans); return 0; }
C 克格涅的照片
给定一个 大小的网格,每个格子 上有一个数 ,初始时会读入 个位置 表示 ,其余位置上的数均为 。你可以无限次将某行或某列的所有数取反,求最少多少次操作后可以使所有位置上的数都是 。此外有 次修改,每次修改会将某一行或某一列取反,在每次修改后输出答案。数据保证始终有解。
有一个显然的结论:在任意操作之后,任意两行的状态只有可能是全等或者是全部相反。读者可以自己手玩一下以理解。
由于数据保证有解,那么我们当前网格的状态也满足这个性质。
于是我们只需要维护第一行 的数量 和与第一行状态不同的行数 ,那么答案要么是将这 行全部变成和第一行相同,再将带 的列取反变为 ,要么是将 行都变为和这 行相同,再将 列取反,故答案为 。
代码:
#include<bits/stdc++.h> using namespace std; #define ri int typedef long long ll; const int maxn=1e6+10; template<class T>inline bool ckmin(T &x,const T &y){return x>y?x=y,1:0;} template<class T>inline bool ckmax(T &x,const T &y){return x<y?x=y,1:0;} template<class T>inline void clear(T *arr,int siz,int val=0){memset(arr,val,sizeof(T)*(siz+1));} int ans[2],k,m,n,q; bool ansx[maxn],ansy[maxn]; int main(){ scanf("%d%d%d%d",&n,&m,&k,&q); while(k--){ ri x,y; scanf("%d%d",&x,&y); if(x==1)ansy[y]^=1; if(y==1)ansx[x]^=1; } if(ansx[1])for(ri i=1;i<=m;++i)ansy[i]^=1; for(ri i=1;i<=n;++i)++ans[ansx[i]]; for(ri i=1;i<=m;++i)++ans[ansy[i]]; printf("%d\n",min(ans[0],ans[1])); while(q--){ ri op,x; scanf("%d%d",&op,&x); if(op)--ans[ansy[x]],ansy[x]^=1,++ans[ansy[x]]; else --ans[ansx[x]],ansx[x]^=1,++ans[ansx[x]]; printf("%d\n",min(ans[0],ans[1])); } return 0; }
D 雷的打字机
一个字符集大小为 的字符串,每次有 的概率向它最后添加字符 ,当出现连续两个相同字符时停止操作。求停止是字符串的期望长度。
设 表示长度为 ,且没有停止的概率。
那么第 个位置的字符存在的概率也为 ,故答案为 。
设 表示长度为 ,最后一个字符为 ,且刚好停止的概率。
长度为 且未停止的字符串往后加两个字符 ,可以视作长度为 且末尾有两个 的字符串,或长度为 且末尾有两个 的字符串再人为加上一个 ,这两种情况的并集。
也就是 。
用 来表示就是 。
对上面这个式子无限求和,有:
然后你发现右边的式子包含所有终止状态,且收敛,故它的值为 。
于是有 。
代码:
#include<bits/stdc++.h> using namespace std; #define ri int typedef long long ll; const int maxn=1e7+10,mod=998244353; template<class T>inline bool ckmin(T &x,const T &y){return x>y?x=y,1:0;} template<class T>inline bool ckmax(T &x,const T &y){return x<y?x=y,1:0;} template<class T>inline void clear(T *arr,int siz,int val=0){memset(arr,val,sizeof(T)*(siz+1));} struct modint{ int val; inline modint(int val_=0):val(val_){} inline modint &operator=(int val_){return val=val_,*this;} inline modint &operator+=(const modint &k){return val=val+k.val>=mod?val+k.val-mod:val+k.val,*this;} inline modint &operator-=(const modint &k){return val=val-k.val<0?val-k.val+mod:val-k.val,*this;} inline modint &operator*=(const modint &k){return val=1ll*val*k.val%mod,*this;} inline modint &operator^=(int k){ modint ret=1,tmp=*this; for(;k;k>>=1,tmp*=tmp)if(k&1)ret*=tmp; return val=ret.val,*this; } inline modint &operator/=(modint k){return *this*=(k^=mod-2);} inline modint &operator+=(int k){return val=val+k>=mod?val+k-mod:val+k,*this;} inline modint &operator-=(int k){return val=val<k?val-k+mod:val-k,*this;} inline modint &operator*=(int k){return val=1ll*val*k%mod,*this;} inline modint &operator/=(int k){return *this*=((modint(k))^=mod-2);} template<class T>friend modint operator+(modint a,T b){return a+=b;} template<class T>friend modint operator-(modint a,T b){return a-=b;} template<class T>friend modint operator*(modint a,T b){return a*=b;} template<class T>friend modint operator^(modint a,T b){return a/=b;} template<class T>friend modint operator/(modint a,T b){return a/=b;} friend modint operator^(modint a,int b){return a^=b;} friend bool operator==(modint a,int b){return a.val==b;} friend bool operator!=(modint a,int b){return a.val!=b;} inline bool operator!(){return !val;} inline modint operator-(){return val?mod-val:0;} inline modint &operator++(){return *this+=1;} }; using mi=modint; mi ans,p[maxn],pre[maxn],suf=1,sum; int n; unsigned s; int main(){ /* f[i][k] 表示刚好停止,长度为 i,最后一个字符为 k 的概率 g[i] 表示未停止,长度为 i 的概率 答案就是 sum(g[i]) (...ax)kk=(...ab)kk+(...akk)k g[i-2]*p[k]^2=f[i][k]+f[i-1][k]*p[k] sum(g[i])*sum(p[k]^2)=sum(sum(f[i][k])*(1+p[k])) sum(g[i])*sum((p[k]^2)/(1+p[k]))=sum(f[i][k]) 显然 sum(f[i][k]) 包含所有终止状态,故它的值为 1 故有 sum(g[i])=1/sum((p[k]^2)/(1+p[k])) n<=1e7,显然出题人是想让我们写一个线性求逆元 但是我并不想写。。。于是继续推式子 1/sum((p[k]^2)/(1+p[k]))=prod(1+p[k])/sum((p[k]^2)*prod_{i!=k}(1+p[i])) 于是一遍前缀积,一遍后缀积就完事了。。。 线性求逆元,狗都不写。。。 */ scanf("%d%u",&n,&s); pre[0]=1; for(ri i=1;i<=n;++i){ if(i<n)s=(s<<2)^(s>>5)^(s<<7)^(s>>11),p[i]=s%998244353; else p[i]=1-sum; pre[i]=pre[i-1]*(1+p[i]); sum+=p[i]; } for(ri i=n;i;--i){ ans+=p[i]*p[i]*pre[i-1]*suf; suf*=(1+p[i]); } printf("%d",pre[n]/ans); return 0; }
E 密涅瓦的谜题
给定一个字符串 , 次询问从 中选出 个子串 (可以为空)顺序拼接起来后可以得到多少本质不同的字符串。
对于这种问题,第一步套路都是每一个串”能划分就划分“。具体而言,一组 合法当且仅当 ,有 加上 的第一个字符后不是 的子串。
令 表示考虑了最后 次选取的子串,当前的第一个字符是 的方案数,只要保证新选取的子串加上 后不是 的子串即可转移
特殊的, 可以为空字符,即第 次选取的是空串。
则有转移
其中 是转移矩阵, 表示满足当前串开头是 、新选取的串开头是 ,且满足上述条件的方案数,可以在 SAM(后缀自动机)上 dp 得到。
令 表示字符集大小,这部分的复杂度为 。
答案为 ,其中 是一个长度为 的行向量,每个位置都是 ; 是一个长度为 的列向量,每个位置表示以其对应字符为开头的串的个数。
由于 次询问的转移矩阵都是一样的,因此可以预处理出转移矩阵的 次幂,可以将复杂度做到 ,无法通过本题。
考虑答案的形式是一个行向量乘上转移矩阵的 次幂再乘上一个列向量。因此可以从前往后维护前缀行向量以及后缀列向量,复杂度为 ,即可通过本题。
代码:
#include<bits/stdc++.h> using namespace std; #define ri int typedef long long ll; const int lim=1e5,maxa=26,maxn=2e5+10,mod=1e9+7; template<class T>inline bool ckmin(T &x,const T &y){return x>y?x=y,1:0;} template<class T>inline bool ckmax(T &x,const T &y){return x<y?x=y,1:0;} template<class T>inline void clear(T *arr,int siz,int val=0){memset(arr,val,sizeof(T)*(siz+1));} struct modint{ int val; inline modint(int val_=0):val(val_){} inline modint &operator=(int val_){return val=val_,*this;} inline modint &operator+=(const modint &k){return val=val+k.val>=mod?val+k.val-mod:val+k.val,*this;} inline modint &operator-=(const modint &k){return val=val-k.val<0?val-k.val+mod:val-k.val,*this;} inline modint &operator*=(const modint &k){return val=1ll*val*k.val%mod,*this;} inline modint &operator^=(int k){ modint ret=1,tmp=*this; for(;k;k>>=1,tmp*=tmp)if(k&1)ret*=tmp; return val=ret.val,*this; } inline modint &operator/=(modint k){return *this*=(k^=mod-2);} inline modint &operator+=(int k){return val=val+k>=mod?val+k-mod:val+k,*this;} inline modint &operator-=(int k){return val=val<k?val-k+mod:val-k,*this;} inline modint &operator*=(int k){return val=1ll*val*k%mod,*this;} inline modint &operator/=(int k){return *this*=((modint(k))^=mod-2);} template<class T>friend modint operator+(modint a,T b){return a+=b;} template<class T>friend modint operator-(modint a,T b){return a-=b;} template<class T>friend modint operator*(modint a,T b){return a*=b;} template<class T>friend modint operator^(modint a,T b){return a/=b;} template<class T>friend modint operator/(modint a,T b){return a/=b;} friend modint operator^(modint a,int b){return a^=b;} friend bool operator==(modint a,int b){return a.val==b;} friend bool operator!=(modint a,int b){return a.val!=b;} inline bool operator!(){return !val;} inline modint operator-(){return val?mod-val:0;} inline modint &operator++(){return *this+=1;} }; using mi=modint; struct mat{ mi a[maxa][maxa]; inline mat(){memset(a,0,sizeof a);} inline mi* operator[](int id){return a[id];} inline mat operator*(const mat &rhs)const{ mat ret; for(ri i=0;i<26;++i) for(ri j=0;j<26;++j) for(ri k=0;k<26;++k) ret.a[i][j]+=a[i][k]*rhs.a[k][j]; return ret; } }a,aa; mi b[maxn][26],e[maxn][26],preb[maxn][26],pree[maxn][26]; inline mat operator^(mat x,ll y){ mat ret; for(ri i=0;i<26;++i)ret.a[i][i]=1; for(;y;x=x*x,y>>=1)if(y&1)ret=ret*x; return ret; } struct node{ int fa,len,nxt[26]; }sm[maxn]; int cnt=1,lst=1,pos[maxn]; inline void extend(int ch,int pp){ int now=++cnt,p=lst; pos[now]=pp; sm[now].len=sm[p].len+1; for(;p&&!sm[p].nxt[ch];p=sm[p].fa)sm[p].nxt[ch]=now; if(!p)sm[now].fa=1; else{ ri q=sm[p].nxt[ch]; if(sm[q].len==sm[p].len+1)sm[now].fa=q; else{ int clone=++cnt; pos[clone]=pp; sm[clone]=sm[q]; sm[clone].len=sm[p].len+1; sm[now].fa=sm[q].fa=clone; for(;p&&sm[p].nxt[ch]==q;p=sm[p].fa)sm[p].nxt[ch]=clone; } } lst=now; } int can[maxn][26],son[maxn][26]; void dfs(int p,int cur){ e[0][cur]+=sm[p].len-sm[sm[p].fa].len; for(ri i=0;i<26;++i)a[cur][i]+=can[(pos[p]+sm[p].len-1)-1][i]-can[pos[p]+sm[sm[p].fa].len-1][i]; for(ri i=0;i<26;++i) if(son[p][i])dfs(son[p][i],cur); else ++a[cur][i]; } int n,q; char s[maxn]; int main(){ scanf("%s",s+1); n=strlen(s+1); for(ri i=n;i;--i)extend(s[i]-'a',i); for(ri i=2;i<=cnt;++i)son[sm[i].fa][s[pos[i]+sm[sm[i].fa].len]-'a']=i; for(ri i=1;i<=n;++i) for(ri j=0;j<26;++j) can[i][j]=can[i-1][j]+(s[i+1]-'a'!=j); for(ri i=0;i<26;++i) if(son[1][i]) dfs(son[1][i],i); for(ri i=0;i<26;++i){ preb[0][i]=b[0][i]=1; pree[0][i]=e[0][i]; } aa=a^lim; for(ri i=1;i<=lim;++i){ for(ri j=0;j<26;++j){ for(ri k=0;k<26;++k) b[i][j]+=b[i-1][k]*aa[k][j],e[i][j]+=a[j][k]*e[i-1][k]; preb[i][j]=preb[i-1][j]+b[i][j],pree[i][j]=pree[i-1][j]+e[i][j]; } } scanf("%d",&q); while(q--){ ll m; scanf("%lld",&m); --m; int hi=m/lim,lo=m%lim; mi ans=1; if(hi) for(ri i=0;i<26;++i) ans+=preb[hi-1][i]*pree[lim-1][i]; for(ri i=0;i<26;++i)ans+=b[hi][i]*pree[lo][i]; printf("%d\n",ans); } return 0; }
F 艾玛的梦
有一张图,每个点 有初始点权 , 的增长速度为 。
定义图的复合:
设函数 ,其中 是一张图, 是一个矩阵且 为图上有向边 的边权,无边则为
若 ,则 。现在给出 ,其中 为只有 个自环且边权为 的图, 中边 的边权为 ,其中 是给定的。并且边 为 。
再给出 ,点 连向 边权为 ,连向 边权为 。此外有 个操作。
记 。
询问操作为求求图 上 关于时间 的多项式对 取模后的答案。
修改操作包括修改 的点权,修改 ,和 修改 中 时刻的 。
首先我们可以根据根据 和 构造 ,
然后考虑 的情况,手算一下,求出 长什么样子。
每一条边的系数大概就是按照如下规则来生产
若 ,则
若 ,则
否则
有了 之后怎么算答案呢?显然我们可以考虑把把 的增长值求导求导求导....导了 次以后,剩下的答案就没用了。最后答案的 其实就是从点 开始走 步,路上边权积乘上停下的点的初始点权的积的总和。最后再积分积回去就行了。
再考虑 的情况,就是可以在某个点上停留,价值乘上 。所以我们暂时不考虑 ,最后再做一个背包即可。
现在暴力就很显然了,每次更改 的时候去更新这个转移数组即可。
但是我们观察发现 必定含有 这一项,而我们矩阵乘法的时候正好又可以抵消掉某些项,这启示我们可以把最后的答案先除去 然后进行观察。
我们观察 的转移矩阵,发现非常有规律!由此并且由于这个特殊的性质,更改一个 只会修改矩阵 个值,我们可以暴力维护!最后用我们得到的系数乘上每个点初始的值就是最终答案了。
由于 操作不超过 个,所以时间复杂度可以接受。而且 操作只是最后乘上的值,所以直接修改即可。
代码:
#include <bits/stdc++.h> #define int long long #define For(i,a,b)for(int i=a,i##end=b;i<=i##end;i++) #define Rof(i,a,b)for(int i=a,i##end=b;i>=i##end;i--) #define rep(i, a)for(int i=1,i##end=a;i<=i##end;i++) using namespace std; const int N=311,p=998244353; struct matrix{ int v[N][N]; int n; matrix(int _n=0){n=_n;memset(v,0,sizeof v);} int* operator [] (int k){return v[k];} }; matrix F[N],R,G,H,tp; int P[N],ini[N],res[N],Hs[N][N],Q[N][N],ans[N][N]; int w[N],iw[N],fac[N],ifa[N]; int n,m,k; void read(int&x){ x=0; char ch=getchar(); while(!isdigit(ch)){if(ch==EOF)return; ch=getchar();} while(isdigit(ch)){x=x*10+(ch-'0'); ch=getchar();} } int add(int x,int y){x+=y; return x>=p ? x-p : x;} int del(int x,int y){x-=y; return x<0 ? x+p : x;} int Mul(int x,int y){return x*y%p;} int inv(int x,int base=p-2){ int res=1; while(base){ if(base&1)res=res*x%p; x=x*x%p; base>>=1; } return res; } void getinv(){ int inv1=inv(n-1,p-2); rep(i,n){ iw[i]=inv(w[i],p-2); rep(j,n){ if(i!=j)H[j][i]=Mul(inv1,iw[i]); else H[j][i]=Mul(inv1,Mul(del(2,n),iw[i])); } } rep(i,n)Rof(j,n,1) Hs[j][i]=add(Hs[j+1][i],H[j][i]); } matrix operator + (matrix A,matrix B){ matrix res=matrix(A.n); rep(i,n)rep(j,n) res[i][j]=add(A[i][j],B[i][j]); return res; } matrix operator * (matrix A,matrix B){ matrix res=matrix(A.n); rep(k,n)rep(i,n)rep(j,n) res[i][j]=add(res[i][j],Mul(A[i][k],B[k][j])); return res; } matrix operator * (matrix A,int k){ matrix res=matrix(A.n); rep(i,n)rep(j,n) res[i][j]=Mul(A[i][j],k); return res; } void Calc(){ matrix res=matrix(n); rep(i,n)res[i][i]=1; int now=1;F[0]=res; fac[0]=ifa[0]=1; For(x,1,n-1){ rep(i,n)rep(j,n) res[i][j]=del(res[i][j],Mul(G[i][1],H[x][j])); For(i,x+1,n)rep(j,n) res[i-x+1][j]=add(res[i-x+1][j],Mul(w[i-x+1],H[i][j])); For(i,x+1,n)rep(j,n) res[i-x][j]=del(res[i-x][j],Mul(w[i-x],H[i][j])); now=Mul(now,x); fac[x]=now; ifa[x]=inv(now,p-2); F[x]=res*ifa[x]; } fac[n]=Mul(fac[n-1],n);ifa[n]=inv(fac[n],p-2); } void initk(){ P[0]=1; int kp=k; rep(i,n){ P[i]=Mul(kp,ifa[i]); kp=Mul(kp,k); } } void GetAns(){ memset(Q,0,sizeof Q); rep(i,n)For(j,0,n)rep(k,n) Q[i][j]=add(Q[i][j],Mul(ini[k],F[j][i][k])); } void output(int x){ For(i,0,n)res[i]=0; For(i,0,n)For(j,0,n-i) res[i+j]=add(res[i+j],Mul(Q[x][i],P[j])); For(i,0,n) printf("%d%c",res[i]," \n"[i==n]); } void work(int x,int y){ rep(i,n){ if(i==x)continue; For(j,0,n)Q[i][j]=del(Q[i][j],Mul(ini[x],F[j][i][x])); } int nw=y,niw=inv(y,p-2),now=1,invn=inv(n-1); int dif1=del(y,w[x]),dif2=Mul(invn,niw),dif3=Mul(dif2,del(2,n)); rep(i,n){ int inv=ifa[i]; int ddif1=Mul(dif1,inv),ddif2=Mul(dif2,inv),ddif3=Mul(dif3,inv); rep(j,n)if(j!=x) F[i][x][j]=add(F[i][x][j],Mul(ddif1,del(Hs[i+1][j],(i+x<=n ? H[i+x][j] : 0)))); rep(j,n){ if(j!=x){ int res=Mul(n-i,w[j]),res2=0; if(i+j<=n)res=del(res,w[j]); if(x>=i+1&&x<=n&&i+j!=x)res=del(res,w[j]),res2=w[j]; F[i][j][x]=(res*ddif2+res2*ddif3)%p; } else{ int res=Mul(n-i,nw),res2=0; if(i+j<=n)res=del(res,nw); if(x>=i+1&&x<=n&&i+j!=x)res=del(res,nw),res2=nw; F[i][j][x]=(res*ddif2+res2*ddif3)%p; } } } rep(i,n){ if(i!=x)G[x][i]=y,H[i][x]=Mul(invn,niw); else G[x][i]=0,H[i][x]=Mul(Mul(invn,del(2,n)),niw); } Rof(i,n,1)Hs[i][x]=add(Hs[i+1][x],H[i][x]); w[x]=nw; iw[x]=niw; For(i,0,n){ Q[x][i]=0; rep(j,n)Q[x][i]=add(Q[x][i],Mul(ini[j],F[i][x][j])); } rep(i,n){ if(i==x)continue; For(j,0,n)Q[i][j]=add(Q[i][j],Mul(ini[x],F[j][i][x])); } } void initini(int x,int y){ int dif=del(y,ini[x]); For(i,0,n)rep(j,n)Q[j][i]=add(Q[j][i],Mul(dif,F[i][j][x])); ini[x]=y; } signed main(){ read(n); G.n=H.n=F[0].n=n; for(int i=1,x;i<=n;++i){ F[i].n=n; read(x);w[i]=x; rep(j,n)if(i!=j)G[i][j]=x; } getinv();read(k); Calc();initk();rep(i,n)read(ini[i]); GetAns();rep(i,n)output(i); read(m); while(m--){ int op,x,y; read(op); if(op==1){read(x);read(y);work(x,y);} else if(op==2){read(x);k=x;initk();} else if(op==3){read(x); read(y);initini(x,y);} else{read(x);output(x);} } return 0; }