【题解】牛客挑战赛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;
}
全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务