All-in at the Pre-flop

2024 牛客多校(10) H
https://ac.nowcoder.com/acm/contest/81605/H

---

题型分析

线性概率模型

题目描述

在一个简化版的赌局中， $A，B$ 两个选手遵循如下规则进行比赛

1. 初始它们各有数量为 $a,b$ 的筹码
2. 每次开局之前，必须全押
3. 开始后每个人有 $\frac{1}{2}$ 的概率获胜，获胜的一方获得另一方的筹码中，与自己相同数量的筹码。
4. 当一个人没有筹码时比赛结束，这个人输了

问：每个人获胜的概率是多少

数据范围

$1≤a,b<998244353,a+b<998244353$

解题思路

设 $p(x)$ 表示在总筹码为 $n$ 时，拥有筹码 $x$ 的人获胜的概率
则

• 当 $x<=\frac{n}{2}$ 时,有 $f(x)=\frac{1}{2}f(0)+\frac{1}{2}f(2x)$
• 当 $x>\frac{n}{2}$ 时,有 $f(x)=\frac{1}{2}f(n)+\frac{1}{2}f(x-(n-x))$

解得 $f(x)=x/n$

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
ll q_pow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
void solve(){
    ll a,b;
    cin>>a>>b;
    cout<<a*q_pow(a+b,mod-2)%mod<<' '<<b*q_pow(a+b,mod-2)%mod;
}