题解：P16807 [蓝桥杯 2026 国 Python A] 桌游足球
ridewindHE
·
·
题解
前置知识
组合数
\begin{aligned}
\binom{x}{y}&=\frac{x!}{y!(x-y)!}\\
\end{aligned}
逆元
## 题意
一共有 $n+m$ 次进球，小蓝进 $n$ 球，小桥进 $m$ 球，每一时刻小蓝进球数均大于等于小桥进球数，求总方案数。
## 思路
### 总方案数
总共有 $n+m$ 个进球，选 $n$ 个给小蓝，那么总方案数就是：
$$
\binom{n+m}{n}
$$
### 非法方案数
如果在某个时刻，小桥进球数大于小蓝进球数那么就是非法的。我们将第一个让小桥反超的位置前的所有进球都翻转翻转后小蓝 $m-1$ 球小桥 $n+1$ 球，那么非法方案数就是：
$$
\binom{n+m}{n+1}
$$
### 合法方案数
那么合法方案数就等于总方案数减去非法方案数，由此可得：
$$
\begin{aligned}
ans&=\binom{n+m}{n}-\binom{n+m}{n+1}\\
&=\frac{(n+m)!}{n!m!}-\frac{(n+m)!}{(n+1)!(m-1)!}\\
&=\frac{(n+m)!}{(n+1)!m!}\big[(n+1)-m\big]\\
&=\frac{(n+m)!}{(n+1)!m!}\big(n+1-m\big)\\
&=\frac{(n+m)!}{(n+1)n!m!}\big(n+1-m\big)\\
&=\frac{1}{n+1}\frac{(n+m)!}{n!m!}\big(n+1-m\big)\\
&=\frac{n+1-m}{n+1}\frac{(n+m)!}{n!m!}\\
&=\frac{n+1-m}{n+1}\binom{n+m}{n}\\
\end{aligned}
$$
## 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int p=998244353;
ll qp(ll a,ll b){//快速幂模板
a%=p;
ll res=1;
while(b){
if(b&1)res=res*a%p;
a=a*a%p;
b>>=1;
}
return res;
}
ll fac[1000010],inv[1000010];
void init(ll n){//预处理阶乘和阶乘的逆元
fac[0]=inv[0]=1;
for(ll i=1;i<=n;i++)fac[i]=fac[i-1]*i%p;
inv[n]=qp(fac[n],p-2);
for(ll i=n-1;i>=1;i--)inv[i]=inv[i+1]*(i+1)%p;
}
ll C(ll x,ll y){//计算组合数
if(x<y)return 0;
return fac[x]*inv[x-y]%p*inv[y]%p;
}
int main(){
int n,m;
cin>>n>>m;
init(n+m);
cout<<(n-m+1)*qp(n+1,p-2)%p*C(n+m,n)%p;//求答案
return 0;
}
```