[组合数取模] BZOJ 4830 [Hnoi2017]抛硬币

习惯性交换 a 和 b 令 b≥a
首先特判 a=b
这时答案为 22a−Ca2a2
其实就是所有情况减去平局的情况 剩下的不是A赢就是B赢 且是对称的 那么除以2
∑Cin∗Cin=∑Cin∗Cn−in=Cn2n

然后如果b>a
我们考虑如果B扔出了 x 个1 y 个0 A扔出了 z 个1 w 个0
如果某一次B没赢 也就是 x≤z 那么 翻转过来必然是B赢了 y>w
现在我们要求的就是本来B赢 翻转后还是B赢的情况 S
答案就是 2a+b+S2
S=∑i=0aCia∑j=1b−a−1Ci+jb=∑i=0a∑j=1b−a−1Ca−ia∗Ci+jb=∑j=1b−a−1Ca+ja+b=∑j=a+1b+1Cja+b

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> abcd;

inline ll Pow(ll a,ll b,ll P){
  ll ret=1; a%=P;
for (;b;b>>=1,a=a*a%P)
if (b&1)
      ret=ret*a%P;
return ret;
}

const int N=2000005;

ll P1,P2,P;
ll pow1[N],pow2[N],pw1[N],pw2[N];

ll a,b; int K;

ll p,p_a,*_pow,*pw,phi;
inline abcd Find(ll x){  
if (!x) return make_pair(1,0);  
  ll tmp=pw[x/p_a%phi]*_pow[x%p_a]%p_a;
  abcd ret=Find(x/p);
return abcd(tmp*ret.first%p_a,x/p+ret.second);  
}  

inline ll C(ll n,ll m,bool div=0){
  p=2; p_a=P1; _pow=pow1; pw=pw1; phi=P1/2;
  abcd t1=Find(n),t2=Find(m),t3=Find(n-m);
  t1.second-=t2.second+t3.second;
  t1.first=t1.first*Pow(t2.first,phi-1,p_a)%p_a*Pow(t3.first,phi-1,p_a)%p_a;
if (div) t1.second--;
  ll a1=Pow(2,t1.second,P1)*t1.first%P1;
  p=5; p_a=P2; _pow=pow2; pw=pw2; phi=P2/5*4;
  t1=Find(n),t2=Find(m),t3=Find(n-m);
  t1.second-=t2.second+t3.second;
  t1.first=t1.first*Pow(t2.first,phi-1,p_a)%p_a*Pow(t3.first,phi-1,p_a)%p_a;
if (div) t1.first=t1.first*((P2+1)>>1)%P2;
  ll a2=Pow(5,t1.second,P2)*t1.first%P2;
return (a1*P2%P*Pow(P2,P1/2-1,P1)+a2*P1%P*Pow(P1,P2/5*4-1,P2))%P;
}

int main(){
  freopen("t.in","r",stdin);
  freopen("t.out","w",stdout);
  pow1[0]=pow2[0]=1; P1=Pow(2,9,1LL<<60),P2=Pow(5,9,1LL<<60);
for (int i=1;i<=512;i++) pow1[i]=pow1[i-1]*(i%2?i:1)%P1;  
for (int i=1;i<=1953125;i++) pow2[i]=pow2[i-1]*(i%5?i:1)%P2;
while (~scanf("%lld%lld%d",&a,&b,&K)){
    P1=Pow(2,K,1LL<<60),P2=Pow(5,K,1LL<<60); P=P1*P2;
    pw1[0]=pw2[0]=1;
for (int i=1;i<=P1/2;i++) pw1[i]=pw1[i-1]*pow1[P1]%P1;
for (int i=1;i<=P2/5*4;i++) pw2[i]=pw2[i-1]*pow2[P2]%P2;

    ll ans;
if (a==b)
      ans=(Pow(2,2*a-1,P)+P-C(2*a,a,1))%P;
else{
      swap(a,b);
      ans=Pow(2,a+b-1,P);
if (~(a+b)&1)
    ans+=C(a+b,(a+b)/2,1);
for (ll j=(a+b)/2+1;j<b;j++)
    ans+=C(a+b,j);
      ans%=P;
    }
    char buf[10];
sprintf(buf,"%%0%dd\n",K);
printf(buf,ans);
  }
return 0;
}