Codeforces 711E ZS and The Birthday Paradox（乘法逆元）

forever97 posted @ 2016年8月30日 22:45 in 数学-乘法逆元 with tags 乘法逆元 , 702 阅读

【题目链接】 http://codeforces.com/problemset/problem/711/E

【题目大意】

假设一年有2^n天，问k个小朋友中有两个小朋友生日相同的概率。　　

假设该概率约分后为 p / q ,输出p , q对1000003取模的解。

【题解】

当k比天数要大时是肯定成立的，否则答案为1-A(2ⁿ,k) / (2ⁿ)^k,

考虑A(2ⁿ,k)=2ⁿ*(2ⁿ-1)*……*（2ⁿ-k+1)，所以分子和分母的最大公约数是2的幂次，暴力计算分子分母，以及计算最大公约数的逆元，就可以计算出答案。

【代码】

#include <cstdio>
typedef long long ll;
ll n,k;
const ll mod=1000003;
ll pow(ll a,ll b,ll p){ll t=1;for(a%=p;b;b>>=1LL,a=a*a%p)if(b&1LL)t=t*a%p;return t;}
int main(){
    scanf("%I64d%I64d",&n,&k);
    if(n<=62&&k>1ll<<n){puts("1 1");return 0;}
    ll num=0; for(ll i=k-1;i;i>>=1)num+=i/2;
    ll b=1,a=pow(2,n,mod);
    for(ll i=1;i<=k-1;i++){
        ll tmp=(a-i+mod)%mod;
        b=b*tmp%mod;
        if(!tmp)break;
    }ll inv=pow(pow(2,num,mod),mod-2,mod);
    a=pow(a,k-1,mod);
    a=a*inv%mod; b=b*inv%mod;
    b=(a-b+mod)%mod;
    printf("%I64d %I64d\n",b,a);
    return 0;
}