题解 P3726 【[AH2017/HNOI2017]抛硬币】

command_block · 2020-04-05 16:07:01 · 题解

题意：Alice 抛 a 次硬币，Bob 抛 b 次硬币，分别得到 c_A,c_B 次正面，若 c_A>c_B，则 Alice 获胜。求她获胜的方案数。

答案对 10^k 取模，多组数据，T\leq 10，b\leq a\leq b+10000，a,b\leq 10^{15}，k\leq 9，时限 \texttt{1s}。

• 前置芝士：范德蒙德卷积 \dbinom{n+m}{k}=\sum\limits_{i=0}^k\dbinom{n}{i}\dbinom{m}{k-i}

a=b

此时两人是平等的，但是获胜条件并不平等，要刨掉平局的情况

根据范德蒙德卷积

除此之外两人就五五开了，方案数是

a>b

注意到 a,b 都很大，a-b 却很小，我们需要使用抵消思想才能利用到 a-b。

将抛硬币的结果记载为 01 序列 A,B。（1 代表正面）

• 记 |A| 为 A 中 1 的个数。

• 记 \overline A 为：将 A 01 取反得到的序列。

• 称 (\overline A,\overline B) 为 (A,B) 的对偶方案。

显然，我么把所有方案分成了一个个对子。我们希望有很多对子是一胜一负，这样它们就能对消。

当 a=b 时，只要 |A|\neq |B|，对子一定是一胜一负，故我们只用关心 |A|=|B| 的方案数。

当 a>b 时，设 A 赢一次输一次的对子个数为 S_1（对偶），赢两次的对子个数为 S_2（不对偶）。（显然 A 不可能一次都不赢）则答案为

又知道 S_1+S_2=2^{a+b-1}，故我们只需要在 S_1,S_2 中求出其一。

直觉告诉我们，由于 a-b 很小，不对偶远少于对偶的情况。故我们考虑计算 S_2.

对子不对偶时，按照定义有 |A|>|B| 且 a-|A|>b-|B| 即 a-b>|A|-|B|。

出现了！a-b！

分别枚举 |B|,|A|-|B| 可得：（注意，每个对子会被统计两次）

注意到有b-i+i+j=b+j，这是个范德蒙德卷积。

使用 a-b 次 ExLucas 计算这些组合数。复杂度O((a-b)\log^2a+5^k+2^k)。

注：2 在\pmod {10^k} 下没有逆元，为了除 2，我们把模数乘 2 再把最后结果直接除 2 即可。

#include<algorithm>
#include<cstdio>
#define MaxN 2005000
#define ll long long
using namespace std;
void exgcd(ll a,ll b,ll &x,ll &y){
  if (b==0){x=1;y=0;return ;}
  exgcd(b,a%b,y,x);y-=(a/b)*x;
}
ll inv(ll a,ll m){
  ll x,y;exgcd(a,m,x,y);
  return (x%m+m)%m;
}
ll powM(ll a,ll t,int mod)
{
  ll ret=1;
  while(t){
    if (t&1)ret=ret*a%mod;
    a=a*a%mod;t>>=1;
  }return ret;
}
struct Data
{
  int p,mod;
  ll sav[MaxN];
  void Init(){
    sav[0]=1;
    for (int i=0;i<mod;i+=p){
      for (int j=i+1;j<i+p;j++)
        sav[j]=sav[j-1]*j%mod;
      sav[i+p]=sav[i+p-1];
    }
  }
  ll v(ll n){
    ll ret=0;
    while(n)ret+=(n/=p);
    return ret;
  }
  ll r(ll n){
    if (n==0)return 1;
    return powM(sav[mod-1],n/mod,mod)*sav[n%mod]%mod*r(n/p)%mod;
  }
  ll C(ll n,ll m)
  {
    ll c=v(n)-v(m)-v(n-m),
       ans=powM(p,c,mod);
    if (!ans)return 0;
    ans=ans*r(n)%mod;
    ans=ans*inv(r(m),mod)%mod;
    ans=ans*inv(r(n-m),mod)%mod;
    return ans;
  }
  ll calc(ll a,ll b)
  {
    if (a==b)return (powM(2,a+b,mod)-C(a<<1,a)+mod)%mod;
    ll ret=0;
    for (int i=1;i<a-b;i++)
      ret+=C(a+b,b+i);
    return (powM(2,a+b,mod)+ret)%mod;
  }
}T2,T5;
ll a,b;int k;
void solve()
{
  T2.mod=2;for (int i=0;i<k;i++)T2.mod*=2;
  T5.mod=1;for (int i=0;i<k;i++)T5.mod*=5;
  T2.Init();T5.Init();
  int mod=T2.mod*T5.mod;
  ll ret=(T2.calc(a,b)*inv(T5.mod,T2.mod)%mod*T5.mod
         +T5.calc(a,b)*inv(T2.mod,T5.mod)%mod*T2.mod)%mod;
  ret>>=1;mod>>=1;
  for (int i=0;i<k;i++){
    printf("%d",ret*10/mod%10);
    mod/=10;
  }puts("");
}
int main()
{
  T2.p=2;T5.p=5;
  while(~scanf("%lld%lld%d",&a,&b,&k))solve();
  return 0;
}