[ABC277G] Random Walk to Millionaire 题解

题目链接

点击打开链接

题目解法

首先 \(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;
}