HNOI2017 抛硬币
主体思路
首先我们发现有\(2^{a+b}\)中硬币情况，在大部分的情况下把每个硬币翻转以后，结果反转。
但是就是有一些特例。
当a=b时，答案形如\(\frac{2^{a+b}-F}{2}\)，其中F表示小A小B抛出来的硬币数相等的情况数，此时反转前后小A都没赢。
于是我们列出式子：
\[F=\sum_{i=0}^n\binom{a}{i}^2=\sum_{i=0}^n\binom{a}{i}\binom{a}{a-i}=\binom{2a}{a}\]
当a>b时，答案形如\(\frac{2^{a+b}+G}{2}\)，其中G表示翻转前后小A都赢的情况数，注意前面相等的情况翻转后结果也会反转，所以不需要减 那么设小A有X个正面，小B有Y个，显然\(X>Y\)且\(a-X>b-Y\)，所以\(0<X-Y<a-b\)。
这样我们又可以列出式子：
\[G=\sum_{i=0}^b\sum_{j=1}^{a-b-1}\binom{b}{i}\binom{a}{i+j}=\sum_{i=1}^{a-b-1}\sum_{j=0}^b\binom{b}{j}\binom{a}{i+j}=\sum_{i=1}^{a-b-1}\sum_{j=0}^b\binom{b}{b-j}\binom{a}{i+j}=\sum_{i=1}^{a-b-1}\binom{a+b}{i+b}\]
然后我们就可以计算出答案\(\times 2\)对\(2\times 10^k\)取膜的值，然后÷2。
复杂度优化
如果直接写，会T成70分。
然后我们需要加上一些优化：
优化1：（每组询问中）由于CRT合并的始终是那两个数，所以可以先计算一次两个数相对对方的逆元，然后可以直接用，于是优化掉了CRT的\(log_2 n\)，然而发现并没有什么用。
优化2：（全局） 由于一直是mod 2^(k+1)和mod 5^k求逆元，我们可以先记录a2[i]表示1..i中不是2倍数的数的积\(\mod 2^{10}\)，a5[i]表示1..i中不是5倍数的数的积\(\mod 5^{9}\)。然后可以直接用，优化力度较大，并且我们还可以把递归搞成非递归强行加速。
然而还是只有70pts。
优化3：（真正的骚操作）我们发现除了k=2的特例，\(a2[2^k]=1\)。并且在1..5^9范围内，\(a5[5^k]=-1\)，然后又可以把快速幂干掉。
然后在不开氧气优化的本机80pts，开O2AC，在洛谷也AC（有O2）
/*
Author: CNYALI_LK
LANG: C++
PROG: coin.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<ll,ll> pii;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
void Write(ll a,ll n){
if(n>1)Write(a/10,n-1);
putchar(a%10+'0');
}
ll read(){
ll s=0,base=1;
char c;
while(!isdigit(c=getchar()))if(c=='-')base=-base;else if(c==EOF)exit(0);
while(isdigit(c)){s=s*10+(c^48);c=getchar();}
return s*base;
}
char WritellBuffer[1024];
template<class T>void write(T a,char end){
ll cnt=0,fu=1;
if(a<0){putchar('-');fu=-1;}
do{WritellBuffer[++cnt]=fu*(a%10)+'0';a/=10;}while(a);
while(cnt){putchar(WritellBuffer[cnt]);--cnt;}
putchar(end);
}
ll Pow(ll a,ll b){
ll c=1;
while(b){
if(b&1)c=c*a;
a=a*a;
b>>=1;
}
return c;
}
ll exgcd(ll a,ll b,ll &x,ll &y){
if(!b){
x=1;y=0;
return a;
}
else{
ll d=exgcd(b,a%b,y,x);
y-=(a/b)*x;
return d;
}
}
ll inv(ll a,ll p){
ll x,y;
exgcd(a,p,x,y);
return (x%p+p)%p;
}
ll t2a,t5a;
ll fpm(ll a,ll b,ll p){
ll c=1;
while(b){
if(b&1)c=c*a%p;
a=a*a%p;
b>>=1;
}
return c;
}
ll mxa,F2,F5;
ll CRT(ll a,ll b){
// printf("%lld %lld !!\n",a,b);
return (a*F5%mxa*t5a+b*F2%mxa*t2a)%mxa;
}
ll js(ll a,ll p){
if(a>=p)return a/p+js(a/p,p);
return 0;
}
ll a2[102424],a5[2333333];
ll fac2(ll a){
ll ans=1,g;
while(a){
ans=ans*a2[a%t2a]%t2a;
a/=2;
}
return ans;
}
ll k;
ll lucas2(ll a,ll b){
ll sa=fac2(a),sb=inv(fac2(b),t2a),sc=inv(fac2(a-b),t2a);
ll ga=js(a,2),gb=js(b,2),gc=js(a-b,2);
ga-=gb+gc;
return sa*sb%t2a*sc%Pow(2,max(k+1-ga,0LL))*Pow(2,ga);
}
ll fac5(ll a){
ll ans=1;
while(a){
ans=ans*a5[a%t5a]%t5a;
if((a/t5a)&1)ans=t5a-ans;
a/=5;
}
return ans;
}
ll lucas5(ll a,ll b){
ll sa=fac5(a),sb=inv(fac5(b),t5a),sc=inv(fac5(a-b),t5a);
ll ga=js(a,5),gb=js(b,5),gc=js(a-b,5);
ga-=gb+gc;
return sa*sb%t5a*sc%Pow(5,max(k-ga,0LL))*Pow(5,ga);
}
int main(){
freopen("coin.in","r",stdin);
freopen("coin.out","w",stdout);
ll a,b;
a2[0]=a5[0]=1;
for(int i=1;i<=1024;++i){
a2[i]=a2[i-1];
if(i&1)a2[i]=a2[i]*i%1024;
}
for(int i=1;i<=1024;i<<=1)printf("%lld\n",(a2[i]-1)%i);
for(int i=1;i<=1953125;++i){
a5[i]=a5[i-1];
if(i%5)a5[i]=a5[i]*i%1953125;
}
printf("G");
for(int i=1;i<=1953125;i*=5)printf("%lld\n",(a5[i]+1)%i);
// printf("%lld %lld\n",a2[1024],a5[1953125]);
while(1){
a=read();b=read();k=read();
mxa=Pow(10,k)*2;
t2a=Pow(2,k+1),t5a=Pow(5,k);
exgcd(t2a,t5a,F2,F5);
F2=(F2%t5a+t5a)%t5a;
F5=(F5%t2a+t2a)%t2a;
ll ans=fpm(2,a+b,mxa);
if(a==b)ans+=mxa-CRT(lucas2(a+a,a),lucas5(a+a,a));
else{
for(ll i=1;i<a-b;++i)ans+=CRT(lucas2(a+b,b+i),lucas5(a+b,b+i));
}
ans%=mxa;
ans/=2;
Write(ans,k);
putchar('\n');
}
return 0;
}