2022-01-28 12:29 已编辑牛客运营

关注

【题解】牛客挑战赛31

A 妈妈的考试

长度为 $n$ 的序列 $s$ ，其中 $s_i\in\{-1,1\}$ ，令 $w_0=\sum\limits_{i=1}^ns_i$ ， $w_1=\sum\limits_{1\le i < j < k \le n}s_is_js_k$ ，你需要求出所有 $2^n$ 种情况中，满足 $w_1>0$ 的最小的 $w_1$ 和满足 $w_0<0$ 的最大的 $w_1$ 。

首先先证一下 $w_0$ 和 $n$ 奇偶性相同：

不妨令所有 $s_i$ 都为 $1$ ，那么此时的 $w_0=n$ ，任意一个 $s_i$ 变为 $-1$ 都会使 $w_0$ 减小 $2$ ，而减去一个偶数，奇偶性不变，故 $w_0$ 和 $n$ 奇偶性相同。

所以我们之后求出的每个答案的合法的前提是 $|w_0|\le n$ 且 $w_0$ 与 $n$ 的奇偶性相同。

然后开始推式子。

$(\sum\limits_{i=1}^ns_i)^3$

$=\sum\limits_{i=1}^ns_i+3\times \sum\limits_{1\le i,j\le n \land i\ne j}s_is_j^2+6\times \sum\limits_{1\le i < j < k \le n}s_is_js_k$

$=\sum\limits_{i=1}^ns_i+3\times \sum\limits_{i=1}^ns_i\sum\limits_{1\le j\le n \land j\ne i}s_j^2+6\times \sum\limits_{1\le i < j < k \le n}s_is_js_k$

$=\sum\limits_{i=1}^ns_i+3(n-1)\times \sum\limits_{i=1}^ns_i+6\times \sum\limits_{1\le i < j < k \le n}s_is_js_k$

将 $w_0,w_1$ 代入，得 $w_0^3=(3n-2)w_0+6w_1$ ，故有 $w_1=\frac{(w_0^3-(3n-2)w_0)}{6}$ 。

可以发现 $w_1$ 和 $w_0$ 是形如 $y=x^3-kx\ (k>0)$ 的函数关系，于是接下来就好办了。（这里建议读者先把这个函数大致的画出来，便于理解后面的内容）

求满足 $w_1>0$ 的最小的 $w_1$

答案肯定会在零点附近取到，而 $x^3-kx=x(x^2-k)$ ，故只需枚举 $-\sqrt{k},0,\sqrt{k}$ 这三个位置附近合法的 $w_0$ 并更新答案即可。
求满足 $w_0<0$ 的最大的 $w_1$ 。

对原函数求导，得 $y'=3x^2-k$ ，观察图像可得 $x=-\sqrt{\frac{k}{3}}$ 的时候为极大值点，枚举其附近合法的 $w_0$ 并更新答案即可。

代码：

#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 克洛涅的多项式

给出一个 $m$ 次多项式 $G(x)$ 以及 $n$ 个数 $x_i$ ，有一个 $n$ 次项系数为 $1$ 的 $n$ 次多项式 $F(x)$ 对于所有的 $x_i$ 均满足 $F(x_i)=G(x_i)$ 。给定一个正整数 $k$ ，求 $F(k)$ 的值。

令 $H(x)=F(x)-G(x)$ ，则有 $H(x_i)=F(x_i)-G(x_i)=0$ 且 $H(x)$ 为一个 $n$ 次多项式，故 $H(x)$ 的零点式为 $H(x)=\prod\limits_{i=1}^n(x-x_i)$ ，则 $F(k)=G(k)+H(k)=G(k)+\prod\limits_{i=1}^n(k-x_i)$ 。

代码：

#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 克格涅的照片

给定一个 $n\times m$ 大小的网格，每个格子 $(i,j)$ 上有一个数 $s_{i,j}\in\{0,1\}$ ，初始时会读入 $k$ 个位置 $(x_i,y_i)$ 表示 $s_{x_i,y_i}=1$ ，其余位置上的数均为 $0$ 。你可以无限次将某行或某列的所有数取反，求最少多少次操作后可以使所有位置上的数都是 $0$ 。此外有 $q$ 次修改，每次修改会将某一行或某一列取反，在每次修改后输出答案。数据保证始终有解。

有一个显然的结论：在任意操作之后，任意两行的状态只有可能是全等或者是全部相反。读者可以自己手玩一下以理解。

由于数据保证有解，那么我们当前网格的状态也满足这个性质。

于是我们只需要维护第一行 $1$ 的数量 $A$ 和与第一行状态不同的行数 $B$ ，那么答案要么是将这 $B$ 行全部变成和第一行相同，再将带 $1$ 的列取反变为 $0$ ，要么是将 $n-B$ 行都变为和这 $B$ 行相同，再将 $m-A$ 列取反，故答案为 $\min(A+B,m-A+n-B)$ 。

代码：

#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 雷的打字机

一个字符集大小为 $n$ 的字符串，每次有 $p_i$ 的概率向它最后添加字符 $i$ ，当出现连续两个相同字符时停止操作。求停止是字符串的期望长度。

设 $g_i$ 表示长度为 $i$ ，且没有停止的概率。

那么第 $i$ 个位置的字符存在的概率也为 $g_i$ ，故答案为 $\sum\limits_{i=1}^ng_i$ 。

设 $f_i^{[k]}$ 表示长度为 $i$ ，最后一个字符为 $k$ ，且刚好停止的概率。

长度为 $i-2$ 且未停止的字符串往后加两个字符 $k$ ，可以视作长度为 $i$ 且末尾有两个 $k$ 的字符串，或长度为 $i-1$ 且末尾有两个 $k$ 的字符串再人为加上一个 $k$ ，这两种情况的并集。

也就是 $(\cdots xy)kk=(\cdots xz)kk+(\cdots xkk)k$ 。

用 $f,g$ 来表示就是 $g_{i-2}p_k^2=f_i^{[k]}+f_{i-1}^{[k]}p_k$ 。

对上面这个式子无限求和，有：

$\Big(\sum\limits_{i\ge 1}g_i\Big)p_k^2=(1+p_k)\Big(\sum\limits_{i\ge 1}f_i^{[k]}\Big)$

$\Big(\sum\limits_{i\ge 1}g_i\Big)\sum\limits_{k=1}^np_k^2=\sum\limits_{k=1}^n(1+p_k)\Big(\sum\limits_{i\ge 1}f_i^{[k]}\Big)$

$\Big(\sum\limits_{i\ge 1}g_i\Big)\sum\limits_{k=1}^n\frac{p_k^2}{1+p_k}=\sum\limits_{k=1}^n\sum\limits_{i\ge 1}f_i^{[k]}$

然后你发现右边的式子包含所有终止状态，且收敛，故它的值为 $1$ 。

于是有 $\sum\limits_{i\ge 1}g_i=\frac{1}{\sum\limits_{k=1}^n\frac{p_k^2}{1+p_k}}$ 。

代码：

#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 密涅瓦的谜题

给定一个字符串 $S$ ， $q$ 次询问从 $S$ 中选出 $m$ 个子串 $t_i$ （可以为空）顺序拼接起来后可以得到多少本质不同的字符串。

对于这种问题，第一步套路都是每一个串”能划分就划分“。具体而言，一组 $(t_1,t_2,\dots,t_m)$ 合法当且仅当 $\forall 1\le i<m$ ，有 $t_i$ 加上 $t_{i+1}$ 的第一个字符后不是 $S$ 的子串。

令 $f_{i,j}$ 表示考虑了最后 $i$ 次选取的子串，当前的第一个字符是 $j$ 的方案数，只要保证新选取的子串加上 $j$ 后不是 $S$ 的子串即可转移

特殊的， $j$ 可以为空字符，即第 $m-i+1$ 次选取的是空串。

则有转移 $f_{i,j}=\sum\limits_k f_{i-1,k}\times A_{k,j}$

其中 $A$ 是转移矩阵， $A_{x,y}$ 表示满足当前串开头是 $x$ 、新选取的串开头是 $y$ ，且满足上述条件的方案数，可以在 SAM（后缀自动机）上 dp 得到。

令 $|\sum|$ 表示字符集大小，这部分的复杂度为 $O(n|\sum|)$ 。

答案为 $B\times A^{m-1}\times E$ ，其中 $B$ 是一个长度为 $|\sum|$ 的行向量，每个位置都是 $1$ ； $E$ 是一个长度为 $|\sum|$ 的列向量，每个位置表示以其对应字符为开头的串的个数。

由于 $q$ 次询问的转移矩阵都是一样的，因此可以预处理出转移矩阵的 $1,2,3,\dots,\sqrt m,2\sqrt m,3\sqrt m,\dots$ 次幂，可以将复杂度做到 $O((\sqrt m+q)|\sum|^3)$ ，无法通过本题。

考虑答案的形式是一个行向量乘上转移矩阵的 $m-1$ 次幂再乘上一个列向量。因此可以从前往后维护前缀行向量以及后缀列向量，复杂度为 $O(\sqrt m|\sum|^2+q|\sum|)$ ，即可通过本题。

代码：

#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 艾玛的梦

有一张图，每个点 $i$ 有初始点权 $d_i$ ， $d_i$ 的增长速度为 $\sum\limits_{(i,j)\in G}d_j\times v_{i,j}$ 。
定义图的复合: $G1 \times G2=G3$
设函数 $A=matrix(G)$ ，其中 $G$ 是一张图， $A$ 是一个矩阵且 $A_{i,j}$ 为图上有向边 $(i,j)$ 的边权，无边则为 $0$
若 $G1 \times G2=G3$ ，则 $matrix(G1)\times matrix(G2)=matrix(G3)$ 。

现在给出 $G1\times G2=G$ ，其中 $G$ 为只有 $n$ 个自环且边权为 $1$ 的图， $G1$ 中边 $(i,j)$ 的边权为 $w_i$ ，其中 $w_i$ 是给定的。并且边 $(i,i)$ 为 $0$ 。
再给出 $G3$ ，点 $i$ 连向 $i+1$ 边权为 $1$ ，连向 $i$ 边权为 $k$ 。

此外有 $q$ 个操作。
记 $G'=G1\times G3\times G2$ 。
询问操作为求求图 $G'$ 上 $d_x$ 关于时间 $t$ 的多项式对 $x^{n+1}$ 取模后的答案。
修改操作包括修改 $G_1$ 的点权，修改 $k$ ，和修改 $G'$ 中 $0$ 时刻的 $d_x$ 。

首先我们可以根据根据 $G$ 和 $G1$ 构造 $G2$ ， $i\not= j$
$G2_{i,j}=\frac{1}{(n-1)*w_j}\\ G2_{i,i}=\frac{(2-n)}{(n-1)*w_j}$

然后考虑 $k=0$ 的情况，手算一下，求出 $G'$ 长什么样子。

每一条边的系数大概就是按照如下规则来生产

若 $i=n$ ，则 $a_{n,j}=[i=1]\frac{w_n}{w_j}$

若 $j=1\lor i+1$ ，则 $a_{i,j}=\frac{(n-2)w_i}{(n-1)w_j}\\$

否则 $a_{i,j}=\frac{-w_i}{(n-1)w_j}\\$

有了 $G'$ 之后怎么算答案呢？显然我们可以考虑把把 $d$ 的增长值求导求导求导....导了 $n$ 次以后，剩下的答案就没用了。最后答案的 $[x^n]$ 其实就是从点 $x$ 开始走 $n$ 步，路上边权积乘上停下的点的初始点权的积的总和。最后再积分积回去就行了。

再考虑 $k\not=0$ 的情况，就是可以在某个点上停留，价值乘上 $k$ 。所以我们暂时不考虑 $k$ ，最后再做一个背包即可。

现在暴力就很显然了，每次更改 $w$ 的时候去更新这个转移数组即可。

但是我们观察发现 $a_{i,j}$ 必定含有 $\frac{w_i}{w_j}$ 这一项，而我们矩阵乘法的时候正好又可以抵消掉某些项，这启示我们可以把最后的答案先除去 $\frac{w_i}{w_j}$ 然后进行观察。

我们观察 $k=0$ 的转移矩阵，发现非常有规律！由此并且由于这个特殊的性质，更改一个 $w$ 只会修改矩阵 $\mathcal O(n)$ 个值，我们可以暴力维护！最后用我们得到的系数乘上每个点初始的值就是最终答案了。

由于 $1$ 操作不超过 $300$ 个，所以时间复杂度可以接受。而且 $2,3$ 操作只是最后乘上的值，所以直接修改即可。

代码：

#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;
}