Atcoder Beginner Contest 298---E

题目：E - Unfair Sugoroku (atcoder.jp)

分析：这题状态转移方程挺好推的，但是用dp解是我没想到的

dp[i][j][0]表示T在i点，A在j点且轮到T走时赢的概率

dp[i][j][1]表示T在i点，A在j点且轮到A走时赢的概率

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
using namespace std;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<int,pair<int,ll>> pil;
typedef unsigned long long ULL;
const ll mod = 998244353;
const int M=1e5+5;
const int N = 1e5+ 5;
ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;
}
int cmp(int a, int b)
{
    return a > b;
}
ll qpow(ll base,ll power)
{
    ll res=1;
    while(power)
    {
        if(power%2)
        {
            res=res*base%mod;
        }
        base=base*base%mod;
        power>>=1;
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n,a,b,p,q;
    cin>>n>>a>>b>>p>>q;
    ll dp[105][105][3];
    memset(dp,0,sizeof(dp));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<2;j++)
        {
            dp[n][i][j]=1;
            dp[i][n][j]=0;
        }
    }
    for(int i=n-1;i>0;i--)
    {
        for(int j=n-1;j>0;j--)
        {
            for(int k=1;k<=p;k++)
            {
                dp[i][j][0]=(dp[i][j][0]+dp[min(i+k,n)][j][1])%mod;

            }
            dp[i][j][0]=(dp[i][j][0]%mod)*qpow(p,mod-2)%mod;
            for(int k=1;k<=q;k++)
            {
                dp[i][j][1]=(dp[i][j][1]+dp[i][min(j+k,n)][0])%mod;
            }
            dp[i][j][1]=dp[i][j][1]%mod*qpow(q,mod-2)%mod;
        }
    }
    cout<<dp[a][b][0];
}