题解 P6630 【[ZJOI2020] 传统艺能】

· · 题解

首先，每个结点都是独立的，所以不妨分开计算贡献。

按照P5280的套路，我们定义 P_o 为 o 上有标记的概率，P_f 为 o 及其祖先上有标记的概率，同时记 o 控制的区间为 [L,R]，o 的父亲的为 [l,r]（可以避免对左/右儿子的分类讨论），修改区间为 [x,y]。

考虑以下五种情况：

  1. 修改不会进入 o 的父亲。则 1\le x\le y<l 或 r<x\le y\le n，此时 P_o'=P_o,P_f'=P_f。
  2. 修改进入 o 的父亲，并在 o 上打了标记。则 1\le x\le L,R\le y<r 或 l<x\le L,R\le y\le n，此时 P_o'=P_f'=1。
  3. 修改标记了 o 的祖先。则 1\le x\le l,r\le y\le n，此时 P_o'=P_o,P_f'=1。
  4. 修改下推了 o 的父亲的标记，但没有进入 o。则 l\le y<L,1\le x\le y 或 R<x\le r,x\le y\le n，此时 P_o'=P_f'=P_f。
  5. 修改进入了 o。则 P_o'=P_f'=0。

显然每次转移的系数都不变，因此可以用矩阵加速。同时，有一个可以大大减小常数的 trick：可以注意到 3\times 3 矩阵中在变化的值只有 5 个，因此只需要计算这 5 个值就可以了，可以将乘法次数减小到 7 次，取模次数减小到 5 次。

code:

#include<cstdio>
typedef long long ll;
const int mod=998244353;
const int BUF=1<<21;
char rB[BUF],*rS,*rT;
inline char gc(){return rS==rT&&(rT=(rS=rB)+fread(rB,1,BUF,stdin),rS==rT)?EOF:*rS++;}
inline int rd(){
    char c=gc();
    while(c<48||c>57)c=gc();
    int x=c&15;
    for(c=gc();c>=48&&c<=57;c=gc())x=x*10+(c&15);
    return x;
}
int n,k,div,ans;
inline void inc(int&a,int b){a+=b;if(a>=mod)a-=mod;}
void exgcd(int a,int b,int&x,int&y){
    if(!b){x=1;y=0;}
    else{
        exgcd(b,a%b,y,x);
        y-=a/b*x;
    }
}
inline int inv(int a){
    int x,y;
    exgcd(a,mod,x,y);
    return x+((x>>31)&mod);
}
struct mat{
    int a11,a12,a13,a22,a23;
    mat(int a,int b,int c,int d,int e):a11(a),a12(b),a13(c),a22(d),a23(e){}
    inline mat operator*(const mat&b)const{return mat((ll)a11*b.a11%mod,((ll)a11*b.a12+(ll)a12*b.a22)%mod,((ll)a11*b.a13+(ll)a12*b.a23+a13)%mod,(ll)a22*b.a22%mod,((ll)a22*b.a23+a23)%mod);}
};
inline int fp(mat a){
    mat s(1,0,0,1,0);
    for(int p=k;p;p>>=1){
        if(p&1)s=s*a;
        a=a*a;
    }
    return s.a13;
}
void solve(int L,int R,int l,int r){
    if(L<R){
        int M=rd();
        solve(L,M,L,R);solve(M+1,R,L,R);
    }
    if(!l)inc(ans,div);  //o 为根节点
    else{
        int a=((ll)l*(l-1)+(ll)(n-r)*(n-r+1)>>1)%mod,b=((ll)L*(r-R)+(ll)(n-R+1)*(L-l))%mod,c=(ll)l*(n-r+1)%mod,d=((ll)(l+L-1)*(L-l)+(ll)(n*2-R-r+1)*(r-R)>>1)%mod;
//a,b,c,d 对应情况 1,2,3,4
        inc(ans,fp(mat((ll)(a+c)*div%mod,(ll)d*div%mod,(ll)b*div%mod,(ll)(a+d)*div%mod,(ll)(b+c)*div%mod)));
    }
}
int main(){
    n=rd();k=rd();div=inv(((ll)n*(n+1)>>1)%mod);
    solve(1,n,0,0);
    printf("%d",ans);
    return 0;
}