题目：
给定$a$张黑牌,$b$白牌，甲，乙两人按以下顺序抽牌：
甲抽一张，乙抽一张，然后弃去一张，然后重复以上过程。
先抽到黑牌者胜，求甲和乙获胜的概率$mod 1004535809$的值。
输入：
一行，两个整数$a b$,分别代表黑牌张数和白牌张数
输出：
一行，两个整数，分别代表甲和乙的胜率
数据范围：
$a,b\leq10000$
样例：
考试之后题解给的是这样的：
然而在我们的电脑上，它T了，然后巨佬renhr想出了以下方法//%%% renhr!!!!
一句微小的提示：以下各式子中除法默认向下取整。
先考虑平局的情况，这种情况下一定是黑牌全部被弃去，因此其概率为：
[\frac{{C_{{\textstyle{{a + b} \over 3}}}^a}}{{C_{a + b}^a}}]
接下来考虑甲胜的情况：
我们枚举在第几局决出胜负，那么在这一局之前，甲乙二人抓到的一定是白牌，在这一局，甲抓到了黑牌，不妨设这是第$i$局，那么将会有$a+b-2*i-3$个位置上的牌的颜色是不确定的，而这些位置上有共计$a-1$张黑牌，因而甲的胜率为：
[\frac{{\sum\limits_{i = 1}^{{\textstyle{{a + b} \over 3}}} {C_{a + b – 2i – 3}^{a – 1}} }}{{C_{a + b}^a}}]
接下来容斥一下，就能得到乙的胜率了。
组合数用线筛逆元即可。
本蒟蒻的代码：跑的比标程快的多
#include
#define mod 1004535809ll
int a,b,n;
long long pin[20100],inv[20100],fw,lw;
void init()
{
pin[0]=1;
for(int i=1;i20010;i++)
pin[i]=pin[i-1]*i%mod;
inv[0]=1;
inv[1]=1;
for(int i=2;i20010;i++)
inv[i]=(mod-mod/i)*inv[mod%i]%mod;
for(int i=2;i20010;i++)
inv[i]=inv[i-1]*inv[i]%mod;
}
long long C(int x,int y)
{
if(x0||y<0)
return 0;
return pin[x]*inv[y]%mod*inv[x-y]%mod;
}
int main()
{
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
init();
scanf("%d%d",&a,&b);
n=a+b;
for(int i=1;i3)
{
fw=(fw+C(n-2*i/3-1,a-1))%mod;
}
long long bas=inv[n]*pin[b]%mod*pin[a]%mod;
long long draw=C(n/3,a)*bas%mod;
fw=fw*bas%mod;
lw=(1-draw-fw+2*mod)%mod;
printf("%lld %lld\n",fw,lw);
return 0;
}
Original: https://www.cnblogs.com/Grharris/p/11770938.html
Author: Grharris
Title: 一道诡异的考试题
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/577990/
转载文章受原作者版权保护。转载请注明原作者出处！