abc298E Unfair Sugoroku 题解

六楼溜刘 · 2023-04-15 22:26:51 · 题解

题意

• 小 A 和小 T 要玩一个骰子游戏，小 T 最初在 A 点，小 A 最初在 B 点。小 T 的骰子上每面的数字分别为 1,2,3\dots P，小 A 的骰子上每面的数字分别为 1,2,3\dots Q。
• 两人轮流扔骰子，我们认为骰子每一面等概率出现（冷知识，现实中骰子每面的概率不同），假如某人扔骰子前在 x 点，扔骰子结果为 i ，则移动到 \min(x+i,N) 点，先到达点 N 的获胜。
• 求先手小 T 获胜的概率。
• 2 \le N \le 100,1 \le A,B \le N,1 \le P,Q \le 10

题解

概率/期望 DP 入门题，简单讲讲。

容易发现这个游戏不可能向后退，符合 DP 的“无后效性”原则。

设计 DP 状态，容易想到令 dp_{i,j,1/0} 表示出现先手玩家在点 i，后手玩家在点 j，这一步轮到先手/后手走这种情况的概率。

接下来考虑转移方程（这里只说先手，后手一样的），显然，由于扔骰子的概率是一致的，故 dp_{i,j,1} 可以等概率地转化到 dp_{i+1,j,0},dp_{i+2,j,0}\dots dp_{i+P,j,0}，使其的概率增加 dp_{i,j,1}\times \frac{1}{p}。

注意到题面中这句话：

移动到 \min(x+i,N) 点。

所以这道题边界处理也非常简单，每次转移时将目标与 N 取 \min 就行了。

这道题初状态就更简单了，令 dp_{A,B,1} 为 1 即可。

答案即为 \sum\limits_{i=b}^ndp_{n,i,0}，由于先手胜前必定是先手走所以下一步（尽管这一步不存在）是后手走，故只用统计第三维为 0 的情况

第一次赛时写出 E 结果 Unrated，QWQ。

code

#include<iostream>
#include<algorithm>
#include<string.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#include<vector>
#define pbk(a) emplace_back(a) 
#define forup(i,s,e) for(ll i=(s);i<=(e);i++)
#define fordown(i,s,e) for(register ll i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline ll read(){//快读。
    ll x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const ll mod=998244353,N=105;
ll ksm(ll a,ll b){//快速幂用来算逆元。
    ll c=1;
    while(b){
        if(b&1) c=(c*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return c;
}
ll n,a,b,p,q;
ll dp[N][N][2];
signed main(){
    n=read();a=read();b=read();p=read();q=read();
    dp[a][b][1]=1;//初状态
    ll invp=ksm(p,mod-2),invq=ksm(q,mod-2);//提前算逆元只用算一次。
    forup(i,a,n-1){
        forup(j,b,n-1){
            forup(k,0,1){//枚举三维
                if(dp[i][j][k]==0) continue;
                if(k){
                    forup(num,1,p){
                        dp[min(i+num,n)][j][0]=(dp[min(i+num,n)][j][0]+dp[i][j][1]*invp%mod)%mod;
                    }
                }else{
                    forup(num,1,q){
                        dp[i][min(j+num,n)][1]=(dp[i][min(j+num,n)][1]+dp[i][j][0]*invq%mod)%mod;
                    }
                }//转移
            }
        }
    }
    int ans=0;
    forup(i,b,n){//注意统计答案要统计后手在所有可能点的情况。
        ans=(ans+dp[n][i][0])%mod;
  //由于先手赢必定是从先手走转移到后手走，只用统计不存在的下一步为后手走的情况。
    }
    printf("%lld",ans);
}