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

可以分别枚举两人正面朝上的次数来统计答案，所求即为

\[\sum_{i=0}^{a}\sum_{j=0}^{b} \binom{a}{i} \binom{b}{j} [i>j]
\]

将\(i\)替换为\(i+j\)来保证\(i>j\)

\[ \begin{aligned}

&\sum_{i=0}^{a}\sum_{j=0}^{b} \binom{a}{i} \binom{b}{j} [i>j] \\

=&\sum_{i=1}^{a}\sum_{j=0}^{a-i} \binom{a}{i+j} \binom{b}{j} \\

=&\sum_{i=1}^{a}\sum_{j=0}^{a-i} \binom{a}{i+j} \binom{b}{b-j}

\end{aligned} \]

由范德蒙德卷积得

\[ \begin{aligned}

&\sum_{i=1}^{a}\sum_{j=0}^{a-i} \binom{a}{i+j} \binom{b}{b-j}\\

=&\sum_{i=1}^{a} \binom{a+b}{b+i} \\

=&\sum_{i=b+1}^{a+b} \binom{a+b}{i}

\end{aligned} \]

直接求化简后的式子复杂度无法接受，但发现\(a\)和\(b\)的差值很小，所以将式子进一步转化得

\[ \begin{aligned}

&\sum_{i=b+1}^{a+b} \binom{a+b}{i} \\

=&\sum_{i=\lceil \frac{a+b}{2} \rceil}^{a+b} \binom{a+b}{i}+\sum_{i=b+1}^{\lfloor \frac{a+b}{2} \rfloor} \binom{a+b}{i}

\end{aligned} \]

第一项的值可以快速计算，当\(a+b\)为奇数时，其为\(2^{a+b-1}\)，当\(a+b\)为偶数时，其为\(2^{a+b-1}-\frac{1}{2}\binom{a+b}{\frac{a+b}{2}}\)，第二项的值用扩展卢卡斯计算组合数即可。

用扩展卢卡斯计算组合数时，可以预处理阶乘和进行特判来优化。

\(code:\)

#include<bits/stdc++.h>

#define maxn 2000010

#define inf 2000000000

using namespace std;

typedef long long ll;

ll a,b,t,k2,k5,mod,ans,x,y;

ll f[6][maxn];

ll exgcd(ll a,ll b)

{

    if(!b)

    {

        x=1,y=0;

        return a;

    }

    ll ans=exgcd(b,a%b),tmp=x;

    x=y,y=tmp-a/b*y;

    return ans;

}

ll inv(ll a,ll p)

{

    if(!a) return 0;

    exgcd(a,p);

    return (x%p+p)%p;

}

ll qp(ll x,ll y,ll p)

{

    ll v=1;

    while(y)

    {

        if(y&1) v=v*x%p;

        x=x*x%p,y>>=1;

    }

    return v;

}

ll fac(ll x,ll p,ll k)

{

    if(!x) return 1;

    return qp(f[p][k],x/k,k)*f[p][x%k]%k*fac(x/p,p,k)%k;

}

ll C(ll n,ll m,ll p,ll k,bool type)

{

    if(n<m) return 0;

    ll sum=0,v=1;

    for(ll i=n;i;i=i/p) sum+=i/p;

    for(ll i=m;i;i=i/p) sum-=i/p;

    for(ll i=n-m;i;i=i/p) sum-=i/p;

    if(type)

    {

        if(p==2) sum--;

        else v=inv(2,k);

    }

    if(sum>=t) return 0;

    return v*fac(n,p,k)%k*qp(p,sum,k)%k*inv(fac(m,p,k),k)%k*inv(fac(n-m,p,k),k)%k;

}

ll crt(ll x,ll p)

{

    return x*inv(mod/p,p)%mod*(mod/p)%mod;

}

ll exlucas(ll n,ll m,bool type)

{

    if(n<m) return 0;

    return (crt(C(n,m,2,k2,type),k2)+crt(C(n,m,5,k5,type),k5))%mod;

}

void init()

{

    f[2][0]=f[5][0]=1;

    for(int i=1;i<=512;++i)

    {

        f[2][i]=f[2][i-1];

        if(i&1) f[2][i]=f[2][i]*i%512;

    }

    for(int i=1;i<=1953125;++i)

    {

        f[5][i]=f[5][i-1];

        if(i%5) f[5][i]=f[5][i]*i%1953125;

    }

}

int main()

{

    init();

    while(scanf("%lld%lld%lld",&a,&b,&t)!=EOF)

    {

        mod=qp(10,t,inf),ans=qp(2,a+b-1,mod),k2=qp(2,t,inf),k5=qp(5,t,inf);

        for(ll i=b+1;i<=(a+b)/2;++i) ans=(ans+exlucas(a+b,i,0))%mod;

        if((a+b)%2==0) ans=(ans-exlucas(a+b,(a+b)/2,1)+mod)%mod;

        printf("%0*lld\n",t,ans);

    }

    return 0;

}

巴特西

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

最新文章

热门文章

巴特西

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

最新文章

热门文章

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