此文章可以使用目录功能哟↑(点击上方[+])
比赛链接→Codeforces Round #369 (Div. 2)
Codeforces Problem 711E ZS and The Birthday Paradox
Accept: 0 Submit: 0
Time Limit: 2 seconds Memory Limit : 256 megabytes
Problem Description
ZS the Coder has recently found an interesting concept called the Birthday Paradox. It states that given a random set of 23 people, there is around 50% chance that some two of them share the same birthday. ZS the Coder finds this very interesting, and decides to test this with the inhabitants of Udayland.
In Udayland, there are 
ZS the Coder knows that the answer can be written as an irreducible fraction 
Input
The first and only line of the input contains two integers n and k (1?≤?n?≤?10^18,?2?≤?k?≤?10^18), meaning that there are
Output
If the probability of at least two k people having the same birthday in
Since these numbers may be too large, print them modulo 10^6?+?3. Note that A and B must be coprime before their remainders modulo 10^6?+?3 are taken.
Sample Input
1 3
4 3
Sample Output
1 1
23 128
Hint
In the first sample case, there are 
In the second sample case, there are only 
Problem Idea
解题思路:
【题意】
在Udayland这个地方,一年有
现在随机调查k个人的生日(生日在哪一天是等可能性的),问至少有两个人生日在同一天的概率是多少
概率用最简分数
【类型】
抽屉原理+乘法逆元+费马小定理+组合数+快速幂+概率论
【分析】
题目求"至少有两个人的生日在同一天的概率"
显然,我们不可能去一一计算两个人生日在同一天的概率、三个人生日在同一天的概率、……、k个人生日在同一天的概率,然后再加起来
因为,一旦k比较大时,计算量也会大得没谱,更何况,概率也不好计算
这时,我们就该从反面考虑考虑
毋庸置疑,相较之下,后者要比前者容易计算
"任意两个人的生日都不在同一天"的情况数相当于从
故"任意两个人的生日都不在同一天"的情况数为
当然,由抽屉原理可以知道,当k>
故当k>
那么剩下的情况,即k≤
∴"至少有两个人的生日在同一天的概率"=
下面我们来计算这一部分:
因为分母
那接下来,问题的关键就是求分子式中有多少个2
对于分子中第i项分子式
例如i=4时,该项分子式有2个2;i=16时,该项分子式有4个2
那最终把每项分子式中2的个数加起来便是tmp值,故约分之后,结果为
因为结果需要取模,于是便涉及到了除法取模,然后理所应当的就需要用到乘法逆元
那么
这时候就需要想到费马小定理
逆元部分也是如此,可以通过费马小定理降幂之后再求解
那分子部分呢?
观察
那么当k-1≥mod时,k-1个连续整数中必有一个能被mod整除,这就意味着取模之后结果为0,那k-1个连续整数的乘积就是0
而当k-1<mod时,因为mod的值不大,所以我们可以暴力循环求出分子
【时间复杂度&&优化】
O(MOD+logk+logn)
题目链接→Codeforces Problem 711E ZS and The Birthday Paradox
Source Code
/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define eps 1e-9
#define LL long long
#define PI acos(-1.0)
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 200005;
const int M = 100005;
const int inf = 1000000007;
const int mod = 1000003;
bool check(__int64 n,__int64 k)
{__int64 s=1;for(int i=1;i<=n;i++){s*=2;if(s>=k)return false;}return true;
}
__int64 Quick_Mod(__int64 a,__int64 b)//快速幂
{__int64 res = 1,term = a % mod;while(b){if(b & 1) res = (res * term) % mod;term = (term * term) % mod;b >>= 1;}return res;
}
int main()
{__int64 n,k,A,B,tmp,i,GCD;scanf("%I64d%I64d",&n,&k);if(check(n,k)){puts("1 1");return 0;}B=Quick_Mod(2,n%(mod-1)*((k%(mod-1)-1+(mod-1))%(mod-1))%(mod-1));for(tmp=0,i=2;i<=k-1;i*=2)tmp+=(k-1)/i;GCD=Quick_Mod(2,tmp%(mod-1)*(mod-2)%(mod-1));B=B*GCD%mod;if(k-1>=mod)printf("%I64d %I64d\n",B,B);else{A=1;for(i=1;i<=k-1;i++)A=A*((Quick_Mod(2,n%(mod-1))-i+mod)%mod)%mod;A=A*GCD%mod;printf("%I64d %I64d\n",(B-A+mod)%mod,B);}return 0;
}