https://www.luogu.org/problemnew/show/P3726

题意：

$A扔a个硬币，B仍b个硬币(a\geq b),求A硬币正面朝上的数量大于B硬币朝上的数量的种类数$A扔a个硬币，B仍b个硬币(a≥b),求A硬币正面朝上的数量大于B硬币朝上的数量的种类数

思路：

我们可以把A和B的硬币种类看成一个01串
比如：$a=3,b=2, 00100$a=3,b=2,00100就代表A的1，2硬币是反面，而3硬币是正面，而B硬币的1，2是反面

我们设A硬币正面朝上的个数为$W_a$Wa​,B硬币正面朝上的为$W_b$Wb​
因为$a\geq b$a≥b 所以我们现在可以把它分为两种情况：

$1.a==b:$1.a==b:

应为$a == b$a==b所以当$W_a &gt; W_b$Wa​>Wb​时，我们把01串反转一下，就变成$W_a&lt;W_b$Wa​<Wb​这样A就输了
所以A赢得情况反转一下，A就输了
那么我们可以得知：总情况=A获胜+B获胜+平局
所以$A获胜=\frac{总情况-平局}{2}$A获胜=2总情况−平局​
$而总情况=2^{a+b},平局=\sum\limits_{i=0}^{b}C_{a}^{i}C_{b}^{i}=\sum\limits_{i=0}^{b}C_{a}^{i}C_{b}^{b-i}=C_{a+b}^{b}(根据范德蒙恒等式)$而总情况=2a+b,平局=i=0∑b​Cai​Cbi​=i=0∑b​Cai​Cbb−i​=Ca+bb​(根据范德蒙恒等式)

范德蒙恒等式

$\sum\limits_{i=0}^{k}C_{a}^{i}C_{b}^{k-i}=C_{a+b}^{k}$i=0∑k​Cai​Cbk−i​=Ca+bk​

继续：

$所以：当a==b:结果为：\frac{2^{a+b}-C_{a+b}^{b}}{2}=\frac{2^{a+a}-C_{2a}^{a}}{2}$所以：当a==b:结果为：22a+b−Ca+bb​​=22a+a−C2aa​​
$这时我们面临一个除于2的问题，因为模数全是10的倍数，所以2在模数下的逆元不存在，$这时我们面临一个除于2的问题，因为模数全是10的倍数，所以2在模数下的逆元不存在，
$因为C_{2a}^{a}=C_{2a-1}^{a}+C_{2a-1}^{a-1}=2C_{2a-1}^{a}\\ 原式=2^{a+b-1}-C_{2a-1}^{a}$因为C2aa​=C2a−1a​+C2a−1a−1​=2C2a−1a​原式=2a+b−1−C2a−1a​

$2.a&gt;b$2.a>b

与a==b的情况类似，我们考虑$W_b&gt;=W_a$Wb​>=Wa​的情况，这时$a-W_a&gt;b-Wb$a−Wa​>b−Wb所以，当B获胜的情况反转一下，A就能获胜
而当有的$Wa&gt;Wb$Wa>Wb时，反转A不一定会输，即当$a-Wa&gt;b-Wb$a−Wa>b−Wb时，A仍然会获胜

类似这种情况
而特殊情况：
$\sum\limits_{i=0}^{b}\sum\limits_{j=1}^{a-b-1}C_{b}^{i}C_{a}^{i+j}\\ =\sum\limits_{i=1}^{a-b-1}\sum\limits_{j=0}^{b}C_{a}^{i+j}C_{b}^{j}\\ =\sum\limits_{i=1}^{a-b-1}\sum\limits_{j=0}^{b}C_{a}^{i+j}C_{b}^{b-j}\\ =\sum\limits_{i=1}^{a-b-1}\sum\limits_{j+k=b+i}C_{a}^{j}C_{b}^{k}$i=0∑b​j=1∑a−b−1​Cbi​Cai+j​=i=1∑a−b−1​j=0∑b​Cai+j​Cbj​=i=1∑a−b−1​j=0∑b​Cai+j​Cbb−j​=i=1∑a−b−1​j+k=b+i∑​Caj​Cbk​
根据前面的范德蒙恒等式
$=\sum\limits_{i=1}^{a-b-1}C_{a+b}^{b+i}$=i=1∑a−b−1​Ca+bb+i​
所以当$a&gt;b$a>b结果为$\frac{2^{a+b}+\sum\limits_{i=1}^{a-b-1}C_{a+b}^{b+i}}{2}$22a+b+i=1∑a−b−1​Ca+bb+i​​
这里我们遇见了一个求和除以2，因为当$i=1$i=1时$C_{a+b}^{b+1}$Ca+bb+1​当$i=a-b-1$i=a−b−1时，$C_{a+b}^{a-1}$Ca+ba−1​，因为$C_{a+b}^{b+1}=C_{a+b}^{a-1}$Ca+bb+1​=Ca+ba−1​
所以这个组合数位于杨辉三角的两侧，我们可以只计算一侧的值就等于除以2了
但是当$a+b是偶数是$a+b是偶数是多出来一个$C_{a+b}^{(a+b)/2}$Ca+b(a+b)/2​，根据前面的可以化简为$2C_{a+b-1}^{(a+b)/2}$2Ca+b−1(a+b)/2​

最后

$a==b时：\\ 2^{a+b-1}-C_{2a-1}^{a}\\ a&gt;b时\\ 2^{a+b-1}+\sum\limits_{i=1}^{(a-b-1)/2}C_{a+b}^{b+i}+[(a+b)\%2==0]C_{a+b-1}^{(a+b)/2}$a==b时：2a+b−1−C2a−1a​a>b时2a+b−1+i=1∑(a−b−1)/2​Ca+bb+i​+[(a+b)%2==0]Ca+b−1(a+b)/2​

结束

AC代码：

#include <bits/stdc++.h>

using namespace std;
#define LL long long
const int Mod = 999911659;
const int maxn = 2e6 + 5;
const double eps = 0.00000001;
const int INF = 2147483647;

LL Pre[2][maxn];
LL d1, d2;
LL a, b, k;

LL extend_gcd(LL a, LL b, LL &x, LL &y) {
    if(!b) {
        x = 1; y = 0;
        return a;
    }
    LL d = extend_gcd(b, a % b, x, y);
    LL t = x;
    x = y; y = t - (a / b) * y;
    return d;
}

LL mul(LL a, LL b, LL P){
    LL L = a * (b >> 25LL) % P * (1LL << 25) % P;
    LL R = a * (b & ((1LL << 25) - 1)) % P;
    return (L + R) % P;
}

LL Pow(LL a, LL b, LL P) {
    LL ans = 1; a %= P;
    while(b) {
        if(b & 1) ans = mul(ans, a, P);
        a = mul(a, a, P);
        b >>= 1;
    }
    return ans;
}

LL getInv(LL a, LL p) {
    LL x, y;
    extend_gcd(a, p, x, y);
    x = (x % p + p) % p;
    return x;
}

LL CRT(LL m, LL p, LL P) {
    return mul(mul(m, (P / p), P), getInv(P / p, p), P);
}

LL Mul(LL n, LL pi, LL pk) {
    if(n <= 1) return 1;
    LL ans = Pow(Pre[pi != 2][pk], n / pk, pk);
    if(n % pk) ans = mul(ans, Pre[pi != 2][n % pk], pk);
    return mul(ans, Mul(n / pi, pi, pk), pk);
}


LL C(LL n, LL m, LL pi, LL pk) {
    if(n < m) return 0;
    LL r = 0;
    for(LL i = n; i; i /= pi) r += i / pi;
    for(LL i = m; i; i /= pi) r -= i / pi;
    for(LL i = n - m; i; i /= pi) r -= i / pi;
    if(r >= k) return 0;
    LL a = Mul(n, pi, pk);
    LL b = getInv(Mul(m, pi, pk), pk);
    LL c = getInv(Mul(n - m, pi, pk), pk);
    LL ans = mul(mul(a, b, pk), c, pk);
    return mul(ans, Pow(pi, r, pk), pk);
}

LL ex_lucas(LL n, LL m, LL P) {
    LL ans = 0;
    ans = (ans + CRT(C(n, m, 2, d1), d1, P)) % P;
    ans = (ans + CRT(C(n, m, 5, d2), d2, P)) % P;
    return ans;
}

void init(LL pi, LL pk) {
    Pre[pi != 2][0] = 1;
    for (int i = 1; i <= pk; i ++) {
        Pre[pi != 2][i] = Pre[pi != 2][i - 1];
        if(i % pi) Pre[pi != 2][i] = mul(Pre[pi != 2][i], i, pk);
    }
}

LL solve(LL a, LL b, LL P) {
    LL ans = Pow(2, a + b - 1, P);
    if(a == b) ans = (ans - ex_lucas(2 * a - 1, a, P) + P) % P;
    else {
        for (int i = 1; i <= (a - b - 1) / 2; i ++)
            ans = (ans + ex_lucas(a + b, b + i, P)) % P;
        if(!((a + b) & 1)) ans = (ans + ex_lucas(a + b - 1, (a + b) / 2, P)) % P;
    }
    return ans;
}

int main()
{
    init(2, 512); init(5, 1953125);
    while(~scanf("%lld %lld %lld", &a, &b, &k)) {
        d1 = Pow(2, k, INF); d2 = Pow(5, k, INF);
        LL P = Pow(10, k, INF);
        LL t = solve(a, b, P);
        while(t < P / 10) {
            printf("0");
            P /= 10;
        }
        printf("%lld\n", t);
    }
    return 0;
}