题目链接
题目解法
首先 \(O(n^3)\) 的 \(dp\) 是显然的，令 \(f_{i,j,k}\) 为第 \(i\) 步在 \(j\)，当前等级为 \(k\) 的 \([i,n]\) 步获得钱数的期望，转移枚举出边即可
一个很妙的优化是：贡献都是 \(k^2\) 的形式，所以我们考虑维护 \(k\) 的 \(0,1,2\) 次幂，即 \(\sum,\sum k,\sum k^2\)，这样可以巧妙的去掉 \(k\) 的一维
时间复杂度 \(O(n^3)\)
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
int FF=0,RR=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
return FF*RR;
}
const int N=3100,P=998244353;
inline void inc(int &x,int y){ x+=y;if(x>=P) x-=P;}
int n,m,k,a[N],gl[N],f[N][N][3];
vector<int> G[N];
int qmi(int a,int b){
int res=1;
for(;b;b>>=1){
if(b&1) res=1ll*res*a%P;
a=1ll*a*a%P;
}
return res;
}
int main(){
n=read(),m=read(),k=read();
F(i,1,m){
int x=read(),y=read();
G[x].pb(y),G[y].pb(x);
}
F(i,1,n) a[i]=read();
F(i,1,n) gl[i]=qmi(G[i].size(),P-2);
DF(i,k,1) F(u,1,n){
for(int v:G[u]){
if(!a[v]){
inc(f[i][u][0],f[i+1][v][0]);
inc(f[i][u][1],(f[i+1][v][1]+f[i+1][v][0])%P);
inc(f[i][u][2],(f[i+1][v][2]+2ll*f[i+1][v][1]+f[i+1][v][0])%P);
}
else{
inc(f[i][u][0],f[i+1][v][0]+1);
inc(f[i][u][1],f[i+1][v][1]),inc(f[i][u][2],f[i+1][v][2]);
}
}
F(k,0,2) f[i][u][k]=1ll*f[i][u][k]*gl[u]%P;
}
printf("%d\n",f[1][1][2]);
fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
return 0;
}