LibreOJ 2023 「AHOI / HNOI2017」抛硬币

需要推推式子的卡常题（

若 a=b，注意到每种小 A 输的方案都可以通过将硬币全部正反翻转与一个赢的方案一一对应。
考虑用总方案数减去平手的方案再除以二即可。
故答案为 2a+b−1−12(2aa)，平手方案可通过范德蒙德卷积公式推出，或考虑组合意义。

若 a>b，则每种小 A 输的和平手的方案都可以与一个赢的方案对应，仅有部分赢的方案独立存在，无法对应。
考虑求这样的方案数。

设小 A 抛出 a′ 枚正面朝上的硬币，小 B 抛出 b′ 枚。
可列出不等式组 {a′>b′a−a′>b−b′。
解得 0<a′−b′<a−b。
观察数据范围，考虑枚举 a′−b′： a−b−1∑i=1b∑j=0(ai+j)(bj)=a−b−1∑i=1b∑j=0(ai+j)(bb−j)=a−b−1∑i=1(a+bb+i)

故答案为 2a+b−1+12a−b−1∑i=1(a+bb+i)。
暴力枚举 i，使用 exLucas 计算即可。

代码：

#include <cstdio>
using namespace std;
const int MX2 = 512;
const int MX5 = 1953125;
int k,k2,k5;
int f[2][MX5 + 5];
long long a,b;
int mod,ans;
inline long long fpow(int a,long long b,int mod)
{
    int ret = 1;
    for(;b;b >>= 1)
        (b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
    return ret;
}
void exgcd(int a,int b,int &x,int &y)
{
    if(!b)
    {
        x = 1,y = 0;
        return ;
    }
    exgcd(b,a % b,x,y);
    int t = x;
    x = y,y = t - a / b * y;
}
int inv(int a,int mod)
{
    int x,y;
    exgcd(a,mod,x,y);
    return (x % mod + mod) % mod;
}
int fac(long long n,int p,int mod)
{
    if(!n)
        return 1;
    return (long long)fpow(f[p == 5][mod] % mod,n / mod,mod) * f[p == 5][n % mod] % mod * fac(n / p,p,mod) % mod;
}
int C(long long n,long long m,int p,int mod,int div2)
{
    if(n < m)
        return 0;
    long long cnt = 0;
    for(register long long i = n;i;i /= p)
        cnt += i / p;
    for(register long long i = m;i;i /= p)
        cnt -= i / p;
    for(register long long i = n - m;i;i /= p)
        cnt -= i / p;
    cnt -= p == 2 && div2;
    if(cnt >= k)
        return 0;
    int ret = (long long)fac(n,p,mod) * inv(fac(m,p,mod),mod) % mod * inv(fac(n - m,p,mod),mod) % mod * fpow(p,cnt,mod) % mod;
    p == 5 && div2 && (ret = (long long)ret * inv(2,mod) % mod);
    return ret;
}
inline int C(long long n,long long m,int div2)
{
    return ((long long)C(n,m,2,k2,div2) * k5 % mod * inv(k5,k2) % mod + (long long)C(n,m,5,k5,div2) * k2 % mod * inv(k2,k5) % mod) % mod;
}
int main()
{
    f[0][0] = f[1][0] = 1;
    for(register int i = 1;i <= MX2;++i)
        i % 2 ? (f[0][i] = (long long)f[0][i - 1] * i % MX2) : (f[0][i] = f[0][i - 1]);
    for(register int i = 1;i <= MX5;++i)
        i % 5 ? (f[1][i] = (long long)f[1][i - 1] * i % MX5) : (f[1][i] = f[1][i - 1]);
    while(~scanf("%lld%lld%d",&a,&b,&k))
    {
        mod = k2 = k5 = 1;
        for(register int i = 1;i <= k;++i)
            mod *= 10,k2 *= 2,k5 *= 5;
        if(a == b)
            ans = (fpow(2,a + b - 1,mod) - C(a + b,a,1)+mod)%mod;
        else
        {
            ans = fpow(2,a + b - 1,mod);
            for(register long long i = (a + b >> 1) + 1;i < a;++i)
                ans = (ans + C(a + b,i,0)) % mod;
            if(!(a + b & 1))
                ans = (ans + C(a + b,a + b >> 1,1)) % mod;
        }
        for(;ans < mod / 10;putchar('0'),mod /= 10);
        printf("%d\n",ans);
    }
    return 0;
}