题面

题解

果然……扩展\(Lucas\)学了跟没学一样……

我们先考虑\(a=b\)的情况，这种情况下每一个\(A\)胜的方案中\(A\)和\(B\)的所有位上一起取反一定是一个\(A\)败的方案，而平局的方案取反之后仍然是一个平局的方案。那么我们可以用总的方案数\(2^{a+b}\)减去平局的次数除以\(2\)就行了。平局的次数我们可以考虑枚举两边扔了多少次正面，那么答案就是

\[ans=\sum_{i=0}^n {n\choose i}^2={2n\choose n}\]

可以这么证明，\({n\choose i}={n\choose n-i}\)，所以\({n\choose i}^2={n\choose i}\times {n\choose n-i}\)，可以看做是左边\(n\)个里取\(i\)个的方案，右边\(n\)个里取\(n-i\)个的方案。然后我们枚举\(i\)，最后就等价于从\(2n\)个物品里选择\(n\)个物品的方案

接下来是\(a>b\)的情况，首先一种\(A\)败或平局的方案取反之后一定是\(A\)胜。然后\(A\)胜取反之后可能还是\(A\)胜。所以我们需要用总方案数加上\(A\)取反之后仍然获胜的方案数再除以\(2\)

设\(W_A\)表示\(A\)获胜的次数，\(W_B\)同理，那么我们就是要满足\(W_A>W_B\)且\(a-W_A>b-W_B\)，化简之后可得\(a-b>W_A-W_B>0\)

那么我们枚举\(W_B\)和\(W_A-W_B\)，有

\[ \begin{aligned} ans &=\sum_{i=0}^b\sum_{j=1}^{a-b-1}{b\choose i}{a\choose i+j}\\ &=\sum_{i=0}^b\sum_{j=1}^{a-b-1}{b\choose b-i}{a\choose i+j}\\ &=\sum_{j=1}^{a-b-1}\sum_{i=0}^b{b\choose b-i}{a\choose i+j}\\ &=\sum_{j=1}^{a-b-1}\sum_{i+k=b+j}{b\choose i}{a\choose k}\\ &=\sum_{j=1}^{a-b-1}{a+b\choose b+j}\\ \end{aligned} \]

然后就\(ok\)了，剩下的用扩展\(Lucas\)计算就行了

//minamoto#include
    
     #define R register#define ll long long#define fp(i,a,b) for(R int i=a,I=b+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)using namespace std;const int N=2e6+5,inf=2147483647;int fac[2][N],P,k,d1,d2,res;ll a,b;inline int mul(R int x,R int y,R int p){return 1ll*x*y-1ll*x*y/p*p;}int ksm(R int x,R ll y,R int p){    R int res=1;    for(;y;y>>=1,x=1ll*x*x%p)if(y&1)res=1ll*res*x%p;    return res;}void exgcd(int a,int b,int &x,int &y){    if(!b)return x=1,y=0,void();    exgcd(b,a%b,y,x),y-=a/b*x;}inline int Inv(int n,int p){    if(!n)return 0;    int x,y;exgcd(n,p,x,y);    x=(x%p+p)%p;return x?x:x+p;}int Fac(ll n,int pi,int pk){    if(!n)return 1;    int res=ksm(fac[pi!=2][pk],n/pk,pk);    return 1ll*res*fac[pi!=2][n%pk]%pk*Fac(n/pi,pi,pk)%pk;}int C(ll n,ll m,int pi,int pk){    if(n
      
       =k)return 0;    int a=Fac(n,pi,pk),b=Fac(m,pi,pk),c=Fac(n-m,pi,pk),res;    res=1ll*a*Inv(b,pk)%pk*Inv(c,pk)%pk*ksm(pi,r,pk)%pk;    return 1ll*res*(P/pk)%P*Inv(P/pk,pk)%P;}int exLucas(ll n,ll m){    if(n
       
        >1))(res+=exLucas(a+b,b+i))%=P;            if(!((a+b)&1))(res+=exLucas(a+b-1,(a+b)>>1))%=P;        }        while(res