[ABC298E] Unfair Sugoroku 题解

Lehe · 2023-04-18 17:19:29 · 题解

概率 \text{dp}。

考虑 dp_{i,j} 表示第一个人到达 i，第二个人到达 j 的概率。容易得知 dp_{a,b} = 1。那么更新的转移式也非常简单。我们可以枚举两个人掷骰子分别掷出的 x 和 y，那么易得转移式 dp_{\min\{n,i+x\},\min\{n,j+y\}}=dp_{\min\{n,i+x\},\min\{n,j+y\}}+dp_{i,j}\times\frac{1}{pq}。

时间复杂度为 O(n^2pq)，可以通过此题。最后，转移一定要写成更新写法，否则会推的非常痛苦，并且容易 WA。

code：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
int n,a,b,p,q,dp[110][110],ans;
int quickpow(int x,int p)
{
    int base=x;
    int ans=1;
    while(p)
    {
        if(p&1)ans=ans*base%mod;
        p>>=1;
        base=base*base%mod;
    }
    return ans%mod;
}
signed main()
{
    cin>>n>>a>>b>>p>>q;
    dp[a][b]=1;
    for(int i=a;i<n;i++)
        for(int j=b;j<n;j++)
            for(int l1=1;l1<=p;l1++)
                for(int l2=1;l2<=q;l2++)
                    dp[min(i+l1,n)][min(j+l2,n)]=(dp[min(i+l1,n)][min(j+l2,n)]+dp[i][j]*quickpow(p,mod-2)%mod*quickpow(q,mod-2)%mod)%mod;
    for(int i=1;i<=n;i++)ans=(ans+dp[n][i])%mod;
    cout<<ans;
    return 0;
}