Luogu

LOJ

分析

因为期望具有线性性，所以可以对每个节点计算它在 $k$ 次操作后有标记的概率，全部加起来即为答案。

考虑 DP。设 $f_{i,j}$ 表示 $i$ 节点在 $j$ 次操作后有标记的概率，$g_{i,j}$ 表示 $i$ 节点在 $j$ 次操作后某个祖先有标记的概率，$h_{i,j}$ 表示 $i$ 节点在 $j$ 次操作后自己和祖先都没有标记的概率。

转移需要再求出 $5$ 个东西：设 $a_i$ 表示一次操作区间完全包含 $i$ 的概率，$b_i$ 表示一次操作区间的两个端点都在 $i$ 的兄弟侧且与兄弟有交的概率（即不能直接给 $i$ 打上标记但能把父亲的标记下传到 $i$ 的概率），$c_i$ 表示一次操作区间与 $i$ 无交的概率，$d_i$ 表示递归到 $i$ 停止并给 $i$ 打上标记的概率（显然等于 $a_i-a_{fa_i}$），$e_i$ 表示递归到 $i$ 的儿子的概率（显然等于 $1-a_i-c_i$）。$a_i,b_i,c_i$ 比较好求所以这里就不写计算方法了，代码里写得很清楚。

这样子就可以得到状态转移方程
$$
\begin{aligned}
f_{i,j}&=(1-e_i)f_{i,j-1}+(b_i+d_i)g_{i,j-1}+d_ih_{i,j-1}\\
g_{i,j}&=(1-e_{fa_i})g_{i,j-1}+a_{fa_i}h_{i,j-1}\\\
h_{i,j}&=e_if_{i,j-1}+e_ig_{i,j-1}+(1-a_i)h_{i,j-1}
\end{aligned}
$$
因为 $k$ 比较大，所以考虑矩阵快速幂
$$
\begin{bmatrix}f_{i,j}&g_{i,j}&h_{i,j}\end{bmatrix}\times\begin{bmatrix}1-e_i&0&e_i\\b_i+d_i&1-e_{fa_i}&e_i\\d_i&a_{fa_i}&1-a_i\end{bmatrix}=\begin{bmatrix}f_{i,j+1}&g_{i,j+1}&h_{i,j+1}\end{bmatrix}
$$
时间复杂度 $\mathcal{O}(27n\log k)$。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=400000+10;
const int mod=998244353;
int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

int S(int x) { return 1ll*x*(x+1)/2%mod; }

int n,k,rt,tot=0;
int ls[N],rs[N],fa[N],L[N],R[N];
int a[N],b[N],c[N],d[N],e[N];

void build(int& o,int l,int r) {
    o=++tot,L[o]=l,R[o]=r;
    if (l==r) return;
    int m=read();
    build(ls[o],l,m),fa[ls[o]]=o;
    build(rs[o],m+1,r),fa[rs[o]]=o;
}

struct Matrix {
    int s[3][3];
    Matrix() { memset(s,0,sizeof(s)); }
    int* operator [](int i) { return s[i]; }
} A,Q;
Matrix operator *(Matrix a,Matrix b) {
    Matrix c;
    for (int k=0;k<3;++k)
        for (int i=0;i<3;++i)
            for (int j=0;j<3;++j)
                c[i][j]=(c[i][j]+1ll*a[i][k]*b[k][j])%mod;
    return c;
}
Matrix qpow(Matrix a,int b) {
    Matrix c; c[0][0]=c[1][1]=c[2][2]=1;
    for (;b;b>>=1,a=a*a) if (b&1) c=c*a;
    return c;
}

int main() {
    n=read(),k=read(); build(rt,1,n);
    for (int i=1,inv=qpow(S(n),mod-2);i<=tot;++i) {
        a[i]=1ll*L[i]*(n-R[i]+1)%mod*inv%mod;
        if (i==1) b[i]=0;
        else if (ls[fa[i]]==i)
            b[i]=1ll*(S(n-L[rs[fa[i]]]+1)-S(n-R[rs[fa[i]]])+mod)*inv%mod;
        else b[i]=1ll*(S(R[ls[fa[i]]])-S(L[ls[fa[i]]]-1)+mod)*inv%mod;
        c[i]=1ll*(S(L[i]-1)+S(n-R[i]))*inv%mod;
        d[i]=(a[i]-a[fa[i]]+mod)%mod;
        e[i]=(1-a[i]+mod-c[i]+mod)%mod;
    }
    int ans=qpow(S(n),mod-2);
    for (int i=2;i<=tot;++i) {
        Q[0][0]=(1-e[i]+mod)%mod,Q[0][1]=0,Q[0][2]=e[i];
        Q[1][0]=(b[i]+d[i])%mod,Q[1][1]=(1-e[fa[i]]+mod)%mod,Q[1][2]=e[i];
        Q[2][0]=d[i],Q[2][1]=a[fa[i]],Q[2][2]=(1-a[i]+mod)%mod;
        A[0][0]=A[0][1]=0,A[0][2]=1;
        A=A*qpow(Q,k);
        ans=(ans+A[0][0])%mod;
    }
    printf("%d\n",ans);
    return 0;
}