P6630 [ZJOI2020] 传统艺能
首先，期望总结点个数等于每个点有标记的期望相加，这是期望的可加性。
那么考虑拆贡献，枚举一个点 \(u\)，用矩阵乘法优化 \(DP\) 计算祂的期望。
设状态：
\(f_{i,1}\) 表示操作了 \(i\) 次，\(u\) 祖先没有懒标记，\(u\) 没有懒标记的期望。
\(f_{i,2}\) 表示操作了 \(i\) 次，\(u\) 祖先没有懒标记，\(u\) 有懒标记的期望。
\(f_{i,3}\) 表示操作了 \(i\) 次，\(u\) 祖先有懒标记，\(u\) 没有懒标记的期望。
\(f_{i,4}\) 表示操作了 \(i\) 次，\(u\) 祖先有懒标记，\(u\) 有懒标记的期望。
现在将操作分为几类：
为了方便，称区间 \(A\) 和区间 \(B\) 相交为祂们交集不为空并且前者不包含后者。
\(A:\) 操作区间与 \(u\) 父亲的区间不相交。
\(B:\) 操作区间与包含 \(u\) 父亲的区间。
\(C:\) 操作区间与 \(u\) 父亲的区间相交，与 \(u\) 的区间不相交。
\(D:\) 操作区间与 \(u\) 父亲的区间相交，与 \(u\) 的区间相交。
\(E:\) 操作区间与 \(u\) 父亲的区间相交，包含 \(u\) 的区间。
然后转移就用这几种操作区更新，用矩阵乘法优化一下。
代码
\(\mathcal O(nk)\) 暴力
#include<bits/stdc++.h>
using namespace std;
namespace IO{
template<typename T>
inline void read(T&x){
x=0;char c=getchar();bool f=0;
while(!isdigit(c)) c=='-'?f=1:0,c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
f?x=-x:0;
}
template<typename T>
inline void write(T x){
if(x==0){putchar('0');return ;}
x<0?x=-x,putchar('-'):0;short st[50],top=0;
while(x) st[++top]=x%10,x/=10;
while(top) putchar(st[top--]+'0');
}
inline void read(char&c){c=getchar();while(isspace(c)) c=getchar();}
inline void write(char c){putchar(c);}
inline void read(string&s){s.clear();char c;read(c);while(!isspace(c)&&~c) s+=c,c=getchar();}
inline void write(string s){for(int i=0,len=s.size();i<len;i++) putchar(s[i]);}
template<typename T>inline void write(T*x){while(*x) putchar(*(x++));}
template<typename T,typename...T2> inline void read(T&x,T2&...y){read(x),read(y...);}
template<typename T,typename...T2> inline void write(const T x,const T2...y){write(x),putchar(' '),write(y...),sizeof...(y)==1?putchar('\n'):0;}
}using namespace IO;
template<int mod>struct Modint{
int z;
Modint(){z=0;}
Modint(int x){x%=mod;z=x<0?x+mod:x;}
Modint(long long x){x%=mod;z=x<0?x+mod:x;}
Modint(short x){x%=mod;z=x<0?x+mod:x;}
Modint(char x){x%=mod;z=x<0?x+mod:x;}
Modint(bool x){x%=mod;z=x<0?x+mod:x;}
friend Modint operator+(Modint t,Modint t2){Modint ans;ans.z=(t.z+t2.z)%mod;return ans;}
friend Modint operator*(Modint t,Modint t2){Modint ans;ans.z=1ll*t.z*t2.z%mod;return ans;}
friend Modint operator-(Modint t,Modint t2){Modint ans;ans.z=(t.z-t2.z)%mod;return ans;}
Modint operator<<(const int t)const{Modint ans;ans.z=(z<<t)%mod;return ans;}
Modint operator>>(const int t)const{Modint ans;ans.z=(z>>t)%mod;return ans;}
Modint&operator+=(const Modint t){z=(z+t.z)%mod;return *this;}
Modint&operator*=(const Modint t){z=1ll*z*t.z%mod;return *this;}
Modint&operator-=(const Modint t){z=(z-t.z)%mod;return *this;}
Modint&operator<<=(const int t){z=(z<<t)%mod;return *this;}
Modint&operator>>=(const int t){z=(z>>t)%mod;return *this;}
friend Modint ksm(Modint a,int b){
Modint ans=1;
while(b){if(b&1) ans=ans*a;a=a*a,b>>=1;}
return ans;
}
friend void read(Modint&z){
int x=0;char c=getchar();bool f=0;
while(!isdigit(c)) c=='-'?f=1:0,c=getchar();
while(isdigit(c)) x=(x*10ll+c-'0')%mod,c=getchar();
f?x=-x:0;
z.z=x;
}
friend void write(Modint x){x.z<0?x.z+=mod:0;write(x.z);}
};
const int mod=998244353,maxn=400010;
#define M Modint<mod>
int n,k,ch[maxn][2],mid[maxn],cnt,rt,fa[maxn],l[maxn],r[maxn];
M f[maxn][10];
void build(int&u,int l,int r){
u=++cnt;
::l[u]=l,::r[u]=r;
if(l==r) return ;
read(mid[u]);
build(ch[u][0],l,mid[u]),build(ch[u][1],mid[u]+1,r);
fa[ch[u][0]]=fa[ch[u][1]]=u;
}
M calc(int x){return (1ll*x*(x+1)/2)%mod;}
M calc2(int l,int r){return calc(n)-calc(l-1)-calc(n-r);}
signed main(){
read(n,k);
build(rt,1,n);
M ans=ksm(calc(n),mod-2);
for(int i=2;i<=cnt;i++){
int l=::l[i],r=::r[i],L=::l[fa[i]],R=::r[fa[i]];
M A,B=M(L)*(n-R+1),C=calc2(L,R)-calc2(l,r),D=calc2(l,r)-M(l)*(n-r+1),E=M(l)*(n-r+1)-B;
A=calc(n)-B-C-D-E;
M inv=ksm(calc(n),mod-2);
A*=inv,B*=inv,C*=inv,D*=inv,E*=inv;
f[1][1]=1,f[1][2]=f[1][3]=f[1][4]=0;
for(int j=2;j<=k+1;j++){
f[j][1]=f[j-1][1]*(A+C+D)+f[j-1][2]*D+f[j-1][3]*D+f[j-1][4]*D;
f[j][2]=f[j-1][1]*E+f[j-1][2]*(A+C+E)+f[j-1][3]*(C+E)+f[j-1][4]*(C+E);
f[j][3]=f[j-1][1]*B+f[j-1][3]*(A+B);
f[j][4]=f[j-1][2]*B+f[j-1][4]*(A+B);
}
ans+=f[k+1][2]+f[k+1][4];
}
write(ans);
return 0;
}
\(\mathcal O(nlog(n))\) 正解
/*
Luogu P6630 [ZJOI2020] 传统艺能
2026-03-18
*/
#include<bits/stdc++.h>
using namespace std;
namespace IO{
template<typename T>
inline void read(T&x){
x=0;char c=getchar();bool f=0;
while(!isdigit(c)) c=='-'?f=1:0,c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
f?x=-x:0;
}
template<typename T>
inline void write(T x){
if(x==0){putchar('0');return ;}
x<0?x=-x,putchar('-'):0;short st[50],top=0;
while(x) st[++top]=x%10,x/=10;
while(top) putchar(st[top--]+'0');
}
inline void read(char&c){c=getchar();while(isspace(c)) c=getchar();}
inline void write(char c){putchar(c);}
inline void read(string&s){s.clear();char c;read(c);while(!isspace(c)&&~c) s+=c,c=getchar();}
inline void write(string s){for(int i=0,len=s.size();i<len;i++) putchar(s[i]);}
template<typename T>inline void write(T*x){while(*x) putchar(*(x++));}
template<typename T,typename...T2> inline void read(T&x,T2&...y){read(x),read(y...);}
template<typename T,typename...T2> inline void write(const T x,const T2...y){write(x),putchar(' '),write(y...),sizeof...(y)==1?putchar('\n'):0;}
}using namespace IO;
template<int mod>struct Modint{
int z;
Modint(){z=0;}
Modint(int x){x%=mod;z=x<0?x+mod:x;}
Modint(long long x){x%=mod;z=x<0?x+mod:x;}
Modint(short x){x%=mod;z=x<0?x+mod:x;}
Modint(char x){x%=mod;z=x<0?x+mod:x;}
Modint(bool x){x%=mod;z=x<0?x+mod:x;}
friend Modint operator+(Modint t,Modint t2){Modint ans;ans.z=(t.z+t2.z)%mod;return ans;}
friend Modint operator*(Modint t,Modint t2){Modint ans;ans.z=1ll*t.z*t2.z%mod;return ans;}
friend Modint operator-(Modint t,Modint t2){Modint ans;ans.z=(t.z-t2.z)%mod;return ans;}
Modint operator<<(const int t)const{Modint ans;ans.z=(z<<t)%mod;return ans;}
Modint operator>>(const int t)const{Modint ans;ans.z=(z>>t)%mod;return ans;}
Modint&operator+=(const Modint t){z=(z+t.z)%mod;return *this;}
Modint&operator*=(const Modint t){z=1ll*z*t.z%mod;return *this;}
Modint&operator-=(const Modint t){z=(z-t.z)%mod;return *this;}
Modint&operator<<=(const int t){z=(z<<t)%mod;return *this;}
Modint&operator>>=(const int t){z=(z>>t)%mod;return *this;}
friend Modint ksm(Modint a,int b){
Modint ans=1;
while(b){if(b&1) ans=ans*a;a=a*a,b>>=1;}
return ans;
}
friend void read(Modint&z){
int x=0;char c=getchar();bool f=0;
while(!isdigit(c)) c=='-'?f=1:0,c=getchar();
while(isdigit(c)) x=(x*10ll+c-'0')%mod,c=getchar();
f?x=-x:0;
z.z=x;
}
friend void write(Modint x){x.z<0?x.z+=mod:0;write(x.z);}
};
const int mod=998244353,maxn=400010;
#define M Modint<mod>
template<typename T,int maxn>struct Matrix{
T a[maxn+10][maxn+10];
Matrix(){memset(a,0,sizeof(a));}
Matrix operator*(const Matrix b){
Matrix c;
for(int i=1;i<=maxn;i++) for(int k=1;k<=maxn;k++) for(int j=1;j<=maxn;j++) c.a[i][j]+=a[i][k]*b.a[k][j];
return c;
}
};
int n,k,ch[maxn][2],mid[maxn],cnt,rt,fa[maxn],l[maxn],r[maxn];
Matrix<M,4>base,f;
void build(int&u,int l,int r){
u=++cnt;
::l[u]=l,::r[u]=r;
if(l==r) return ;
read(mid[u]);
build(ch[u][0],l,mid[u]),build(ch[u][1],mid[u]+1,r);
fa[ch[u][0]]=fa[ch[u][1]]=u;
}
M calc(int x){return (1ll*x*(x+1)/2)%mod;}
M calc2(int l,int r){return calc(n)-calc(l-1)-calc(n-r);}
signed main(){
read(n,k);
build(rt,1,n);
M ans=ksm(calc(n),mod-2);
for(int i=2;i<=cnt;i++){
int l=::l[i],r=::r[i],L=::l[fa[i]],R=::r[fa[i]];
M A,B=M(L)*(n-R+1),C=calc2(L,R)-calc2(l,r),D=calc2(l,r)-M(l)*(n-r+1),E=M(l)*(n-r+1)-B;
A=calc(n)-B-C-D-E;
M inv=ksm(calc(n),mod-2);
A*=inv,B*=inv,C*=inv,D*=inv,E*=inv;
memset(&f,0,sizeof(f));
f.a[1][1]=1;
base.a[1][1]=A+C+D,base.a[1][2]=D,base.a[1][3]=D,base.a[1][4]=D;
base.a[2][1]=E,base.a[2][2]=A+C+E,base.a[2][3]=C+E,base.a[2][4]=C+E;
base.a[3][1]=B,base.a[3][2]=0,base.a[3][3]=A+B,base.a[3][4]=0;
base.a[4][1]=0,base.a[4][2]=B,base.a[4][3]=0,base.a[4][4]=A+B;
int c=k;
while(c){
if(c&1) f=base*f;
base=base*base;
c>>=1;
}
ans+=f.a[2][1]+f.a[4][1];
}
write(ans);
return 0;
}
浙公网安备 33010602011771号