题解-HNOI2017 抛硬币

Problem

loj2023

题意概述：甲抛掷 (a) 次硬币，乙抛掷 (b) 次硬币，问有多少种情况甲正面向上的次数比乙多，答案对 (10^k) 取模

对于 (10%) 的数据，(a,ble 20)；
对于 (30%) 的数据，(a,ble 100)；
对于 (70%) 的数据，(a,ble 100000)，其中有 (20%) 的数据满足 (a=b)；
对于 (100%) 的数据，(1le a,ble {10}^{15}, ble ale b+10000, 1le kle 9)，数据组数小于等于 (10)

10分

枚举俩人的抛掷方式，存下来合并后统计（没有存在的意义） (O(2^a+2^b+ab))

30分

(sum_{i=1}^abinom aisum_{j=0}^{min(b,i-1)}binom bj)，组合数需预处理 (O(ab))

+20分

由于整个游戏是绝对公平的，即甲赢的概率与乙相当，考虑所有情况减去平局再除以(2)，得到 (frac {2^{a+b}-sum_{i=0}^abinom ai^2}2=frac {2^{a+b}-binom {2a}a}2)

70分

考虑预处理 (f(i)=sum_{j=0}^{min(b,i-1)}binom bj)，再枚举 (i) 求和 (O(a+b))

（+20分与70分部分由于模数非质数则需crt或将阶乘拆解成(kcdot 2^xcdot 5^y)的形式进行模拟除法）

100分

由+20做法可扩展，只需再加上甲赢且对称局面乙赢不了的情况再整体除以(2)即可，关键在于求新加的这个东西

设甲抛掷 (a) 次，得 (x) 次正面；乙抛掷 (b) 次，得 (y) 次正面

则当前情况甲赢，且对称情况乙赢不了（对称情况可以是平局）可以列出式子

[ begin{cases} x>y\ a-xgeq b-y end{cases} ]

已知 (a,b)，解出 (0<x-yleq a-b)，则这一部分的答案已经可以表示为

[sum_{y=0}^bsum_{x=y+1}^{y+(a-b)}binom axbinom by]

由于 (a,b) 都很大，但 (a-bleq 10^4)，从此入手，将其提出来

[sum_{t=1}^{a-b}sum_{y=0}^bbinom a{y+t}binom by]

考虑之前+20的做法中(sumbinom ai^2=sumbinom aibinom a{a-i}=binom {2a}a)，这里后面(sum binom a{y+t}binom by=sum binom a{y+t}binom b{b-y}=binom {a+b}{(y+t)+(b-y)}=binom {a+b}{b+t})

则后面答案为 (sum_{t=1}^{a-b}binom {a+b}{b+t})

则整体答案为

[frac {2^{a+b}-binom {2a}a+sum_{t=1}^{a-b}binom{a+b}{b+t}}2]

由于需要模合数，需要使用(mathsf {exLucas})解决……

至于如何除以 (2)，可以将模数翻倍，最后直接除以 (2)

然后就TLE爆零了 分数不如暴力70，除此之外，还需要注意一些卡常技巧（从(60s+)到(3s)的华丽蜕变)

模数优化

由于模数只能是(10^k)，所以可以考虑只模(10^9)，最后再模(10^k)，可以保证模数唯一，从而预处理模数的质因子分解

模数的质因子只有 (2) 和 (5)，可以储存下来，对应的 (p^k) 分别为 (2^{10},5^9)

（到这里能拿 (30) 分啦）

调用优化

（优化效果特明显）

将两个模数开两个namespace，每个namespace内部由于模数相等，不需要传递模数

（到这里能拿 (70) 分啦）

组合数

由于 (binom nm = binom n{n-m})

而得到的式子 (sum_{t=1}^{a-b}binom{a+b}{b+t}) 中以 (frac {a+b}2) 为中心轴，两侧组合数对称，只要算一半即可（中间值特判一下）

Fac优化

由于每次询问的组合数下标都是 (a+b)，所以可以在每组数据中预处理出 (Fac(a+b))，就不用每次重新调用了

预处理

(p^k)以内除去(p)的阶乘 是可以预处理的，同样 (p^k) 也是可以预处理的

至于是否要预处理所有 除去 (p) 的阶乘，由于询问次数较少，预处理耗时不比直接询问快

（到这里能拿 (100) 分啦）

玄学优化

（优化效果最明显）

若在函数 C(ll n,ll m,ll pi,ll pk)中，算出的 (k) 若比 (pk) 的幂次大，则直接返回 0ll

HN的题真毒，考场上遇到这题还是不要写正解，写了也被卡常

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int p = 2e9;
const int pw2 = 1024;
const int pw5 = 1953125;

int fac[2][pw5+2];
int Pw [2][pw5+2];

void exgcd(ll a,ll b,ll&x,ll&y){
    if(!b){x = 1, y = 0; return ;}
    exgcd(b,a%b,y,x); y -= a/b*x;
}

inline ll inv(ll n,ll mod){
    ll x,y; exgcd(n,mod,x,y);
    return (x+mod)%mod;
}

namespace Lucas2{
    const int pi = 2;
    const int pk = pw2;
    ll k_n;int Fac_n;
    
    inline ll inv(ll n){ll x,y; exgcd(n,pk,x,y);return (x+pk)%pk;}
    inline ll qpow(ll A,ll B){ll res(1ll);while(B){if(B&1)res=res*A%pk;A=A*A%pk,B>>=1;}return res;}
    
    ll Fac(ll n){
        if(!n) return 1ll;
        ll res = 1ll;
        res = fac[0][pk];
        res = qpow(res,n/pk);
        res = res * fac[0][n%pk]%pk;
        return res * Fac(n/pi)%pk;
    }

    inline ll C(ll n,ll m){
        ll k = k_n;
        for(ll i = m; i; i/=pi) k -= i/pi;
        for(ll i=n-m; i; i/=pi) k -= i/pi;
        if(k>=10) return 0ll;
        ll d0 = Fac_n;
        ll d1 = Fac(m);
        ll d2 = Fac(n-m);
        return d0 * inv(d1)%p * inv(d2)%p * Pw[0][k]%pk;
    }
    
    inline ll CRT(ll b){return b * inv(p/pk)%p * (p/pk)%p;}
    
    inline void pre(ll n){
        Fac_n = Fac(n),k_n = 0ll;
        for(ll i = n; i; i/=pi)k_n += i/pi;
    }
}

namespace Lucas5{
    const int pi = 5;
    const int pk = pw5;
    ll k_n;int Fac_n;
    
    inline ll inv(ll n){ll x,y; exgcd(n,pk,x,y);return (x+pk)%pk;}
    inline ll qpow(ll A,ll B){ll res(1ll);while(B){if(B&1)res=res*A%pk;A=A*A%pk,B>>=1;}return res;}
    
    ll Fac(ll n){
        if(!n) return 1ll;
        ll res = 1ll;
        res = fac[1][pk];
        res = qpow(res,n/pk);
        res = res * fac[1][n%pk]%pk;
        return res * Fac(n/pi)%pk;
    }

    inline ll C(ll n,ll m){
        ll k = k_n;
        for(ll i = m; i; i/=pi) k -= i/pi;
        for(ll i=n-m; i; i/=pi) k -= i/pi;
        if(k>=9) return 0ll;
        ll d0 = Fac_n;
        ll d1 = Fac(m);
        ll d2 = Fac(n-m);
        return d0 * inv(d1)%p * inv(d2)%p * Pw[1][k]%pk;
    }
    
    inline ll CRT(ll b){return b * inv(p/pk)%p * (p/pk)%p;}
    
    inline void pre(ll n){
        Fac_n = Fac(n),k_n = 0ll;
        for(ll i = n; i; i/=pi)k_n += i/pi;
    }
}

ll exLucas(ll n,ll m){
    ll res = 0ll;
        res += Lucas2::CRT(Lucas2::C(n,m));
        res += Lucas5::CRT(Lucas5::C(n,m));
    return res%p;
}

char ss[10];
void print(int x,int pp){
    x%=(int)pow(10,pp);
    ss[0] = '%', ss[1] = '0';
    sprintf(ss+2,"%ddn",pp);
    printf(ss,x);
}

void prework(int a,int b){
    int*arr=fac[a==5];
    int*trr= Pw[a==5];
    arr[0]=trr[0]=1;
    for(int i=1;i<=b;++i){
        trr[i] = (ll)trr[i-1]*a%b;
        arr[i] = arr[i-1];
        if(i%a)arr[i]=(ll)arr[i]*i%b;
    }
}

inline ll qpow(ll A,ll B){
    ll res(1ll);while(B){
        if(B&1) res = res*A%p;
        A = A*A%p, B>>=1;
    }return res;
}

int main(){
    ll a,b;int pp;
    prework(2,pw2);
    prework(5,pw5);
    while(~scanf("%lld%lld%d",&a,&b,&pp)){
        ll res = qpow(2,a+b);
        Lucas2::pre(a+b);
        Lucas5::pre(a+b);
//      res = (res - exLucas(a+b,a)+p)%p;
//      for(int i=1;i<=a-b;++i) res = (res + exLucas(a+b,b+i))%p;
        if(a == b){
            res = (res - exLucas(a+b,a)+p)%p;
            print(res>>1,pp); continue;
        }
        for(ll i=(a+b-1>>1);i!=b;--i)
            res = (res + 2ll*exLucas(a+b,i))%p;
        if(0 == ((a+b)&1))
            res = (res + exLucas(a+b,a+b>>1))%p;
        print(res>>1,pp);
    }
    return 0;
}