方案数啊。。。

要么DP要么组合数。

想了一会DP之后发现复杂度太高。

考虑组合数,考虑赢的方案数。

记$w_a>w_b$表示$a$赢了。

那么方案数就是$\sum\limits_{i=0}^a\sum\limits _{j=0}^{i-1}C_{a}^iC_{b}^j$

复杂度还是太高了。

苦思冥想之后发现,这里一定有我不会的东西。

分类讨论吧。

如果$a==b$,平的方案反转之后还是平的。

赢的方案$w_a>w_b $反转之后$a-w_a<b-w_b$是输的。

输的方案反转之后是赢的。

那么也就是总方案数$-$平的方案数$=$赢的方案数$/2$

平的方案数这么算:$\sum\limits _{i=0}^a (C_a^i)^2=\sum\limits_{i=0}^aC_a^{a-i}C_a^i=C_{2a}^a$

这个是根据范德蒙德卷积:$\sum_{i+j=k}C_{n}^iC_{m}^j=C_{n+m}^k$

中文意思很好理解:从$n$个物品中任意选$i$个,从$m$个物品中选$j$个,实际上就是从$n+m$个物品中选$i+j=k$个。

具体证明可用二项式定理。

考虑$a>b$的情况,平的反转之后就是胜的,负的反转之后是胜的。

胜的反转之后可能是胜的,可能是负的,还可能是平的。

对于胜的反转之后还是胜的(也就是正邪不两立的),只要认为补上这一段$01$串,那就有了配对。

就可以(总方案数+01串的数量)$/2$

条件:$w_a>w_b$且$a-w_a>b-w_b$

可以推导出:$a-b>w_a-w_b>0$

可以写成

$\sum\limits _{i=0}^b\sum\limits _{j=1}^{a-b-1}C_{b}^iC_{a}^{i+j}=\sum\limits _{i=0}^{a-b-1}\sum\limits _{j=1}^{b}C_{b}^{b-j}C_{a}^{i+j}$

由于$b-j+i+j=b+i$

可以写成

$\sum\limits _{i=0}^{a-b-1}\sum _{j+k=b+i} C_{b}^{j}C_{a}^{k}$

根据范德蒙德卷积,有$\sum\limits _{i=0}^{a-b-1}\sum _{j+k=b+i} C_{b}^{j}C_{a}^{k}=\sum\limits _{i=0}^{a-b-1}C_{a+b}^{b+i}$

答案就为:

$(a==b):\frac{2^{a*b}-C_{2a}^a}{2}\\(a>b):\frac{2^{a*b}-\sum\limits _{i=0}^{a-b-1}C_{a+b}^{b+i}}{2}$

计算$\sum\limits _{i=0}^{a-b-1}C_{a+b}^{b+i}$,对于$a+b$为奇数,只用计算一半,对于偶数,要特殊处理$C_{a+b}^{(a+b)/2}$,

由杨辉三角可以得知:$C_{a+b}^{(a+b)/2}=C_{a+b-1}^{(a+b)/2}+C_{a+b-1}^{(a+b)/2-1}=2C_{a+b-1}^{(a+b)/2}$

最后使用一下扩展$lucas$定理即可。

可以参照这篇