首页 > 代码库 > Codeforces 711E ZS and The Birthday Paradox（乘法逆元）
Codeforces 711E ZS and The Birthday Paradox（乘法逆元）
【题目链接】 http://codeforces.com/problemset/problem/711/E
【题目大意】
假设一年有2^n天，问k个小朋友中有两个小朋友生日相同的概率。
假设该概率约分后为 p / q ,输出p , q对1000003取模的解。
【题解】
当k比天数要大时是肯定成立的，否则答案为1-A(2n,k) / (2n)k,
考虑A(2n,k)=2n*(2n-1)*……*（2n-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;}
Codeforces 711E ZS and The Birthday Paradox（乘法逆元）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。