牛客周赛80-不公平对局

记忆化搜索dp

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
int mod = 1e9 + 7;
typedef long long ll;
int qmi(int a,int b,int p){ //快速幂
    int res = 1;
    while(b){
        if(b&1) res= res*a%p;
        b >>=1;
        a = a*a%p;
    }
    return res;
}
void solve() {
    int x;
    int a1,b1,a2,b2;
    cin>>x>>a1>>b1>>a2>>b2;
    int p1 = a1 * qmi(b1,mod - 2,mod) % mod;    //计算小红吃掉棋子的概率
    int p2 = a2 * qmi(b2,mod - 2,mod) % mod;    //计算小紫吃掉棋子的概率
    /**
     * 计算四种情况的概率
     */
    int P1 = p1 * p2 % mod;
    int P2 = p1 * (mod + 1 - p2) % mod;
    int P3 = (mod + 1 - p1) * p2 % mod;
    int P4 = (mod + 1 - p1) * (mod + 1 - p2) % mod;
    //由方程推出需要计算P5
    int P5 = (mod + 1 - P4) % mod;
    int inv = qmi(P5,mod - 2,mod); 
    vector<vector<int>> dp(x+1,vector<int>(x+1,-1));
    /**
     * dfs，记忆化搜索，dfs(i,j)表示小红吃掉i个棋子，小紫吃掉j个棋子，小红获胜的概率
     * dfs(i,j) = P1 * dfs(i+1,j+1) + P2 * dfs(i+1,j) + P3 * dfs(i,j+1) + P4 * dfs(i,j)
     * 解方程移项得:dfs(i,j) = (P1 * dfs(i+1,j+1) + P2 * dfs(i+1,j) + P3 * dfs(i,j+1)) / (1 - P4 )
    **/
    auto dfs = [&](auto dfs,int c1,int c2) -> int {
        //递归的出口
        if(c1 == x){    //如果小红下满棋盖，就无法获胜
            return dp[c1][c2] = 0;
        }else if(c2 == x){  //如果小紫下满棋盖，就一定获胜
            return dp[c1][c2] = 1;
        }
        /**
         * 记忆化搜索，如果以及有了，就不用递归计算了
         */
        if(dp[c1][c2] != -1){   
            return dp[c1][c2];
        }
        int A = P1 * dfs(dfs,c1 + 1,c2 + 1) % mod;
        int B = P2 * dfs(dfs,c1 + 1,c2) % mod;
        int C = P3 * dfs(dfs,c1,c2 + 1) % mod;
        return dp[c1][c2] = (A + B + C) % mod * inv % mod;
    };
    cout<<dfs(dfs,0,0)<<endl;   //入口，代表小红和小紫初始没放棋子的状态
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int tt = 1;
    // cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}