题面

主体思路

首先我们发现有$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;
}

标签: 组合

添加新评论