题解：P8208 [THUPC 2022 初赛] 骰子旅行

· · 题解

题解

考虑如何定义 f_{i,j} 表示在第 i 次摇骰子之前到达 j 的期望，f_{i,j} 的转移似乎是显然的：

f_{i,j} = \sum _{j \in son_k} \frac {f_{i-1,k}} {m_k}

其中 son_k 表示 k 能一次到达的点。

考虑再定义一个 g_{i,j,k} 表示对于第 i 次摇骰子之前到达点 j，经过 k 的答案的期望。

转移要分情况讨论：

g_{i,j,k} = \frac {f_{i-1,k} \times j} {m_k} + \sum _{j \in son_l \land k \not = l} \frac {g_{i-1,l,k}} {m_l}

显然的是以上两个转移考虑我为人人似乎更简单，答案就是：\sum _{i=1} ^{T+1} \sum _{j=1} ^{n} g_{i,j,j}，记得处理一下逆元即可，复杂度为 O(n^2 \sum m)，其中 \sum m \le 5000，可以轻松通过。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#ifdef _WIN32
#define getchar _getchar_nolock
#define putchar _putchar_nolock
#else
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
#define pll pair<ll,ll>
#define pld pair<ld,ld>
typedef long long ll;
typedef long double ld;
typedef __int128 i128;
namespace io {
    using namespace std;
    template <typename T> void debug (T x) {
        cerr<<x<<'\n';
    }
    template <typename T> void debuglen (T x) {
        cerr<<x<<' ';
    }
    template <typename T,typename...Args> void debug (T x,Args...args) {
        cerr<<x<<' ';
        debug(args...);
    }
    template <typename T> void debug (T*lt,T*rt) {
        ll len=rt-lt;
        for (ll i=0;i<len;i++) {
            debuglen(*(lt+i));
        }
        cerr<<'\n';
    }
    inline ll read () {
        char x=getchar();
        ll ans=0,f=1;
        while (x<'0'||x>'9') {
            if (x=='-') {
                f=-1;
            }
            x=getchar();
        }
        while (x>='0'&&x<='9') {
            ans=(ans<<1)+(ans<<3);
            ans+=(x^'0');
            x=getchar();
        }
        return ans*f;
    }
    void print (ll x) {
        if (x<0) {
            x=-x;
            putchar('-');
        }
        if (x>=10) {
            print(x/10);
        }
        putchar(x%10+'0');
    }
}
using namespace io;
const ll N=1e2+5,mod=998244353,inf=2e18;
const ld eps=1e-6;
ll n,s,t,f[N][N],g[N][N][N];
vector<ll> v[N];
inline ll qpow (ll x,ll y) {
    ll cnt=1;
    while (y) {
        if (y&1) {
            cnt=cnt*x%mod;
        }
        x=x*x%mod;
        y>>=1;
    }
    return cnt;
}
inline void solve () {
    n=read(),s=read(),t=read();
    for (ll i=1;i<=n;i++) {
        ll k=read();
        while (k--) {
            v[i].push_back(read());
        }
    }
    f[1][s]=1;
    for (ll i=1;i<=t;i++) {
        for (ll j=1;j<=n;j++) {
            if (!f[i][j]) {
                continue;
            }
            ll vm=qpow(v[j].size(),mod-2);
            for (auto it : v[j]) {
                f[i+1][it]+=f[i][j]*vm%mod;
                if (f[i+1][it]>=mod) {
                    f[i+1][it]-=mod;
                }
                for (ll k=1;k<=n;k++) {
                    if (k==j) {
                        g[i+1][it][k]+=f[i][j]*it%mod*vm%mod;
                        if (g[i+1][it][k]>=mod) {
                            g[i+1][it][k]-=mod;
                        }
                        continue;
                    }
                    g[i+1][it][k]+=g[i][j][k]*vm%mod;
                    if (g[i+1][it][k]>=mod) {
                        g[i+1][it][k]-=mod;
                    }
                }
            }
        }
    }
    ll sum=0;
    for (ll i=1;i<=n;i++) {
        for (ll j=1;j<=t+1;j++) {
            sum+=g[j][i][i];
            if (sum>=mod) {
                sum-=mod;
            }
        }
    }
    print(sum);
}
int main () {
    // freopen("travel.in","r",stdin);
    // freopen("travel.out","w",stdout);
    ll T=1;
    // T=read();
    while (T--) {
        solve();
    }
    return 0;
}