需要推推式子的卡常题（
若 \(a=b\)，注意到每种小 A 输的方案都可以通过将硬币全部正反翻转与一个赢的方案一一对应。
考虑用总方案数减去平手的方案再除以二即可。
故答案为 \(2^{a+b-1} - \frac12\binom{2a}a\)，平手方案可通过范德蒙德卷积公式推出，或考虑组合意义。
若 \(a>b\)，则每种小 A 输的和平手的方案都可以与一个赢的方案对应，仅有部分赢的方案独立存在，无法对应。
考虑求这样的方案数。
设小 A 抛出 \(a'\) 枚正面朝上的硬币，小 B 抛出 \(b'\) 枚。
可列出不等式组 \(\begin{cases}a' > b' \\ a-a' > b-b'\end{cases}\)。
解得 \(0 < a'-b' < a-b\)。
观察数据范围，考虑枚举 \(a'-b'\)： \[
\begin{aligned}
\sum\limits_{i=1}^{a-b-1} \sum\limits_{j=0}^b \binom a{i+j} \binom bj
&= \sum\limits_{i=1}^{a-b-1} \sum\limits_{j=0}^b \binom a{i+j} \binom b{b-j} \\
&= \sum\limits_{i=1}^{a-b-1} \binom{a+b}{b+i} \\
\end{aligned}
\]
故答案为 \(2^{a+b-1} + \frac12\sum\limits_{i=1}^{a-b-1} \binom{a+b}{b+i}\)。
暴力枚举 \(i\)，使用 exLucas 计算即可。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
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;
}