不公平对局
📌 题目类型：概率 DP / 数学期望 ⏱️ 时间限制：1 秒 💾 空间限制：1024 M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！ 
题目描述
小红和小紫正在对弈。在围棋规则中，每吃掉对方的一枚棋子，就需要将这枚棋子放入棋盖中。然而，棋盖空间不大，她们任何一方吃子数量达到
x
x
x 就输了。
当然，我们不需要考虑具体的对弈局面，模型简化如下，每个回合将会依次执行以下两步：
- 小红有
p
1
p_1
p1 的概率吃掉对方一枚棋子； - 小紫有
p
2
p_2
p2 的概率吃掉对方一枚棋子。
谁吃子数量达到
x
x
x 就输了。小红执黑先手，她想知道自己最终获胜的概率是多少？你需要将答案对
(
10
9
+
7
)
(10^9 + 7)
(109+7) 取模后输出。
输入描述
第一行输入一个正整数
x
(
1
≤
x
≤
10
3
)
x \\ (1 \\le x \\le 10^3)
x (1≤x≤103)，代表棋盒的容量。
第二行输入两个整数
a
1
,
b
1
(
0
≤
a
1
≤
b
1
≤
10
9
)
a_1, b_1 \\ (0 \\le a_1 \\le b_1 \\le 10^9)
a1,b1 (0≤a1≤b1≤109)，代表小红每回合吃子概率是
p
1
=
a
1
b
1
p_1 = \\dfrac{a_1}{b_1}
p1=b1a1。
第三行输入两个整数
a
2
,
b
2
(
0
≤
a
2
≤
b
2
≤
10
9
)
a_2, b_2 \\ (0 \\le a_2 \\le b_2 \\le 10^9)
a2,b2 (0≤a2≤b2≤109)，代表小紫每回合吃子概率是
p
2
=
a
2
b
2
p_2 = \\dfrac{a_2}{b_2}
p2=b2a2。
除此之外，保证
a
1
,
a
2
a_1, a_2
a1,a2 不同时为
0
0
0。
输出描述
可以证明答案可以表示为一个不可约分数
p
q
\\dfrac{p}{q}
qp，为了避免精度问题，请直接输出整数
(
p
⋅
q
−
1
m
o
d
M
)
(p \\cdot q^{-1} \\bmod M)
(p⋅q−1modM) 作为答案，其中
M
=
10
9
+
7
M = 10^9 + 7
M=109+7，
q
−
1
q^{-1}
q−1 是满足
q
×
q
−
1
≡
1
(
m
o
d
M
)
q \\times q^{-1} \\equiv 1 \\pmod M
q×q−1≡1(modM) 的整数。
更具体地，你需要找到一个整数
x
∈
[
0
,
10
9
+
7
)
x \\in [0, 10^9 + 7)
x∈[0,109+7) 满足
x
×
q
x \\times q
x×q 对
10
9
+
7
10^9 + 7
109+7 取模等于
p
p
p，您可以查看样例解释得到更具体的说明。
⚠️ 本题的数据保证，最终不可约分数的分母
q
q
q 保证不是
(
10
9
+
7
)
(10^9 + 7)
(109+7) 的倍数。
样例展示
样例 1
输入：
10
0 1
1 2
输出：
1
说明：
在这个样例中，小紫每回合有
1
2
=
50
%
\\dfrac{1}{2} = 50\\%
21=50% 的概率吃掉小红一枚棋子，但小红永远不会吃子，所以小紫必败。
样例 2
输入：
1
1 1
1 1
输出：
0
说明：
在这个样例中，每回合双方各有
100
%
100\\%
100% 的概率吃子，但由于小红先手，所以小红的棋盖最先放不下。
样例 3
输入：
1
1 2
1 2
输出：
333333336
说明：
在这个样例中，最终计算得到的结果是
1
3
\\dfrac{1}{3}
31，我们能够找到，
333333336
×
3
=
1000000008
333333336 \\times 3 = 1000000008
333333336×3=1000000008，对
10
9
+
7
10^9 + 7
109+7 取模后恰好等于分子
1
1
1，所以
333333336
333333336
333333336 是需要输出的答案。
解题思路
本题是有限状态概率 DP + 吸收马尔可夫链方程求解的经典问题。核心是定义二维状态表示双方当前吃子数，根据一回合内双方先后吃子的四种组合概率建立带自环的转移方程，通过移项消去自环后倒序递推，最终得到小红获胜概率。
1. 问题等价转化
- 胜负条件：任一方吃子数达到
x
x
x 就输。设小红已吃子数为i
i
i，小紫已吃子数为j
j
j。当i
=
x
i=x
i=x 时小红输，概率为0
0
0；当j
=
x
j=x
j=x 时小紫输，小红赢，概率为1
1
1。 - 状态定义：令
f
[
i
]
[
j
]
f[i][j]
f[i][j] 表示当前小红已吃i
i
i 子、小紫已吃j
j
j 子时，小红最终获胜的概率。 - 一回合的转移：每回合小红先手以概率
p
1
p_1
p1 吃子，小紫后手以概率p
2
p_2
p2 吃子。从状态(
i
,
j
)
(i,j)
(i,j) 出发，下一状态有四种：- 小红吃、小紫不吃：概率
p
1
(
1
−
p
2
)
p_1(1-p_2)
p1(1−p2)，转移到(
i
+
1
,
j
)
(i+1,j)
(i+1,j)； - 小红不吃、小紫吃：概率
(
1
−
p
1
)
p
2
(1-p_1)p_2
(1−p1)p2，转移到(
i
,
j
+
1
)
(i,j+1)
(i,j+1)； - 小红吃、小紫也吃：概率
p
1
p
2
p_1p_2
p1p2，转移到(
i
+
1
,
j
+
1
)
(i+1,j+1)
(i+1,j+1)； - 两人都不吃：概率
(
1
−
p
1
)
(
1
−
p
2
)
(1-p_1)(1-p_2)
(1−p1)(1−p2)，仍停留在(
i
,
j
)
(i,j)
(i,j)。
- 小红吃、小紫不吃：概率
2. 转移方程与自环处理
根据全概率公式：
f
[
i
]
[
j
]
=
p
1
(
1
−
p
2
)
f
[
i
+
1
]
[
j
]
+
(
1
−
p
1
)
p
2
f
[
i
]
[
j
+
1
]
+
p
1
p
2
f
[
i
+
1
]
[
j
+
1
]
+
(
1
−
p
1
)
(
1
−
p
2
)
f
[
i
]
[
j
]
f[i][j] = p_1(1-p_2)f[i+1][j] + (1-p_1)p_2 f[i][j+1] + p_1p_2 f[i+1][j+1] + (1-p_1)(1-p_2) f[i][j]
f[i][j]=p1(1−p2)f[i+1][j]+(1−p1)p2f[i][j+1]+p1p2f[i+1][j+1]+(1−p1)(1−p2)f[i][j] 该方程含有自环项
f
[
i
]
[
j
]
f[i][j]
f[i][j]，将其左移合并：
(
1
−
(
1
−
p
1
)
(
1
−
p
2
)
)
f
[
i
]
[
j
]
=
p
1
(
1
−
p
2
)
f
[
i
+
1
]
[
j
]
+
(
1
−
p
1
)
p
2
f
[
i
]
[
j
+
1
]
+
p
1
p
2
f
[
i
+
1
]
[
j
+
1
]
(1-(1-p_1)(1-p_2)) f[i][j] = p_1(1-p_2)f[i+1][j] + (1-p_1)p_2 f[i][j+1] + p_1p_2 f[i+1][j+1]
(1−(1−p1)(1−p2))f[i][j]=p1(1−p2)f[i+1][j]+(1−p1)p2f[i][j+1]+p1p2f[i+1][j+1] 于是：
f
[
i
]
[
j
]
=
p
1
(
1
−
p
2
)
f
[
i
+
1
]
[
j
]
+
(
1
−
p
1
)
p
2
f
[
i
]
[
j
+
1
]
+
p
1
p
2
f
[
i
+
1
]
[
j
+
1
]
1
−
(
1
−
p
1
)
(
1
−
p
2
)
f[i][j] = \\frac{p_1(1-p_2)f[i+1][j] + (1-p_1)p_2 f[i][j+1] + p_1p_2 f[i+1][j+1]}{1-(1-p_1)(1-p_2)}
f[i][j]=1−(1−p1)(1−p2)p1(1−p2)f[i+1][j]+(1−p1)p2f[i][j+1]+p1p2f[i+1][j+1] 所有概率均在模
10
9
+
7
10^9+7
109+7 意义下用逆元表示，分母的逆元用费马小定理求出。
3. 边界条件与递推顺序
- 边界：
-
f
[
i
]
[
x
]
=
1
f[i][x] = 1
f[i][x]=1（0
≤
i
<
x
0 \\le i < x
0≤i<x），小紫先达到x
x
x，小红获胜； -
f
[
x
]
[
j
]
=
0
f[x][j] = 0
f[x][j]=0（0
≤
j
<
x
0 \\le j < x
0≤j<x），小红先达到x
x
x，小红失败。
-
- 递推顺序：由于转移涉及
i
+
1
i+1
i+1 和j
+
1
j+1
j+1，需要从大下标向小下标倒序计算。双重循环 i 从x
−
1
x-1
x−1 到0
0
0，j 从x
−
1
x-1
x−1 到0
0
0，保证所需后续状态已算出。 - 初始答案：
f
[
0
]
[
0
]
f[0][0]
f[0][0] 即双方均未吃子时小红最终获胜的概率。
4. 复杂度分析
- 时间复杂度：状态数
O
(
x
2
)
O(x^2)
O(x2)，每个状态O
(
1
)
O(1)
O(1) 转移，总O
(
x
2
)
O(x^2)
O(x2)。x
≤
10
3
x \\le 10^3
x≤103，约10
6
10^6
106 次运算，完全可行。 - 空间复杂度：
O
(
x
2
)
O(x^2)
O(x2) 存储 DP 表，10
6
10^6
106 规模内存充足。
总结
将游戏建模为带自环的马尔可夫链，列出全概率方程并移项消去自环，得到可直接递推的 DP 公式。边界条件直观，倒序双重循环实现简单。概率值通过模意义下的乘法逆元处理，最终输出
f
[
0
]
[
0
]
f[0][0]
f[0][0]。
代码简要说明
n
n
n（即容量
x
x
x）及概率分数
a
1
,
b
1
,
a
2
,
b
2
a_1,b_1,a_2,b_2
a1,b1,a2,b2，计算
x
=
a
1
⋅
b
1
−
1
m
o
d
M
x = a_1 \\cdot b_1^{-1} \\bmod M
x=a1⋅b1−1modM，
y
=
a
2
⋅
b
2
−
1
m
o
d
M
y = a_2 \\cdot b_2^{-1} \\bmod M
y=a2⋅b2−1modM。
(
n
+
1
)
×
(
n
+
1
)
(n+1)\\times(n+1)
(n+1)×(n+1) 的二维数组
f
f
f，边界设为：
-
f
[
n
]
[
i
]
=
0
f[n][i] = 0
f[n][i]=0，i
=
0..
n
−
1
i=0..n-1
i=0..n−1； -
f
[
i
]
[
n
]
=
1
f[i][n] = 1
f[i][n]=1，i
=
0..
n
−
1
i=0..n-1
i=0..n−1； -
f
[
n
]
[
n
]
f[n][n]
f[n][n] 任意（不影响）。
-
x
x
=
1
−
x
xx = 1-x
xx=1−x，y
y
=
1
−
y
yy = 1-y
yy=1−y； -
k
=
inv
(
1
−
x
x
⋅
y
y
)
k = \\text{inv}(1 – xx \\cdot yy)
k=inv(1−xx⋅yy)，即转移方程的分母逆元。
for (ll j=n–1; j>=0; j—)
f[i][j] = k * ((x*yy*f[i+1][j] + xx*y*f[i][j+1] + x*y*f[i+1][j+1]) % mod) % mod;
f
[
0
]
[
0
]
f[0][0]
f[0][0]。
代码内容
#include <bits/stdc++.h>
using namespace std;
#define endl '\\n'
typedef long long ll;
typedef unsigned long long ull;
typedef vector<vector<ll>> vvt;
typedef pair<ll,ll> pll;
const ll N=1e3+10;
const ll INF=1e18;
const ll M=1e6+10;
const ll mod=1e9+7;
ll qp(ll x,ll p)
{
ll r=1;
while(p)
{
if(p&1) r=r*x%mod;
x=x*x%mod;
p>>=1;
}
return r;
}
ll invv(ll x){return qp(x,mod–2);}
ll sol()
{
ll n; cin>>n;
ll a1,b1,a2,b2; cin>>a1>>b1>>a2>>b2;
ll x=a1*invv(b1)%mod, y=a2*invv(b2)%mod;
vector<vector<ll>> f(n+1,vector<ll>(n+1));
f[n][n]=0;
for(ll i=0;i<n;i++){f[n][i]=0; f[i][n]=1;}
ll xx=(1–x+mod)%mod, yy=(1–y+mod)%mod, k=invv((1–xx*yy%mod+mod)%mod);
for(ll i=n–1;i>=0;i—)
for(ll j=n–1;j>=0;j—)
f[i][j]=k*(((x*yy%mod*f[i+1][j]%mod+xx*y%mod*f[i][j+1])%mod+x*y%mod*f[i+1][j+1])%mod)%mod;
return f[0][0];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cout<<sol()<<endl;
return 0;
}
