C++ 解法, 执行用时: 165ms, 内存消耗: 15736K, 提交时间: 2021-05-21 17:52:16

#include<cstdio>
using namespace std;
typedef long long ll;
ll v[3], pri[3], xinv[3], fac[6][2000000];
inline ll qp(ll a, ll x, ll mod){
    ll i = 1;
    for(;x;x >>= 1, a = a * a % mod)if(x & 1)i = i * a % mod;
    return i;
}
inline ll cal(ll n, ll p, ll pr){
	return n ? qp(fac[p][pr - 1], n / pr, pr) * fac[p][n % pr] % pr * cal(n / p, p, pr) % pr : 1;
}
inline void exgcd(ll a, ll b, ll &x, ll &y, ll p){
	if(!b)x = 1, y = 0;
	else{
		exgcd(b, a % b, y, x, p);
		y -= a / b * x;
	}
}
inline ll getinv(ll a, ll p){
	ll x, y;
	if(!a)return 0;
	exgcd(a, p, x, y, p);
	return (x % p + p) % p;
}
inline ll getfac(ll n, ll m, ll p, ll pr){
	if(n < m)return 0;
	ll i, j;
	for(i = n, j = 0;i;i /= p)j += i / p;
	for(i = m;i;i /= p)j -= i / p;
	for(i = n - m;i;i /= p)j -= i / p;
	if(j >= 9)return 0;
	ll x = cal(n, p, pr), y = cal(m, p, pr), z = cal(n - m, p, pr);
	return qp(p, j, pr) * x % pr * getinv(y, pr) % pr * getinv(z, pr) % pr;
}
inline ll lucas(ll n, ll m, ll p){
	ll i, j;
	if(n < m)return 0;
	for(i = 1, j = 0;i <= v[0];i++)j = (j + xinv[i] * getfac(n, m, pri[i], v[i]) % p) % p;
	return j;
}
int main(){
	ll a, b, k, p, i;
	v[0] = 2;pri[1] = 2;pri[2] = 5;
	for(k = 1;k <= 2;k++)
		for(i = fac[pri[k]][0] = 1, v[k] = qp(pri[k], 9, 2e9);i < v[k];i++){
			fac[pri[k]][i] = fac[pri[k]][i - 1];
			if(i % pri[k])fac[pri[k]][i] = fac[pri[k]][i] * i % v[k];
		}
	while(~scanf("%lld%lld%lld", &a, &b, &k)){
		for(i = 1;i <= 2;i++)v[i] = qp(pri[i], k, 2e9);
		for(p = v[i = 1] * v[2];i <= 2;i++)xinv[i] = v[3 - i] * getinv(v[3 - i], v[i]) % p;
		k = qp(2, a + b - 1, p);
		if(a == b)k = (k - lucas(a + b - 1, a, p) + p) % p;
		else{
			for(i = b + 1;i <= (a + b - 1) / 2;i++)k = (k + lucas(a + b, i, p)) % p;
			if(a + b & 1 ^ 1)k = (k + lucas(a + b - 1, a + b >> 1, p)) % p;
		}
		while(k < p / 10)putchar('0'), p /= 10;
        printf("%lld\n", k);
	}return 0;
}