CF711E ZS and The Birthday Paradox 题解

1. 题意

   求一年有 $2^n$ 天，$m$ 个人出现两人生日相同的概率。答案输出对 $10^6+3$ 的取模分子和分母（约分后）。

2. 思路

   • 首先想不进行优化的数学计算方法，求出两人生日相同的概率不容易，但我们可以求出所有人生日不同的概率（也就是排列数除以所有情况数），再用 $1$ 减掉，即得公式

     $p=1-\frac{A_{2^n}^{m}}{2^{nm}}$

     展开 $A^m_{2^n}$ 得到

     $p=1-\frac{\left(2^{n}\right)\left(2^{n}-1\right)\left(2^{n}-2\right)\cdots\left(2^{n}-m+1\right)}{2^{nm}}$

   • 然后可以很容易想到用快速幂进行进行计算，求得分子和分母。

   • 但是，题目要求约分。容易看出，分数线上下同除的数一定是 $2^k$（因为分母是$2^{nm}$），且分子一定有剩余（不然答案就是 $0$ 了），因此只要知道分子中可以分解出几个 $2$ 就可以了。

   • 于是，可以使用勒让德定理（但我不会证明）。

     ${v_p\left(n!\right)=\underset{i=1}{\overset{\infty}{\sum}}\lfloor\frac{n}{p^{i}}\rfloor}$

     （$v_p(x)$ 表示 $x$ 质因数分解后 $p$ 的指数）

   • 这样，分子中可以分解出几个 $2$ 就可以用勒让德定理求出。

     下面讲一下具体的方法：

     • 首先想到的是用 $v_2(2^n!)-v_2((2^n-m)!)$ 算出结果，但 $1\le n \le 10^{18}$，显然TLE。

     • 然后想到分类讨论分子的各个组成部分，首先， $2^n$ 中一定有 $n$ 个 $2$，然后考虑之后每一项，可知每一项中 $2$ 的个数取决于减去的数中 $2$ 的个数，即而所有除 $2^n$ 之外的项中 $2$ 的个数就是每次减去的数中 $2$ 的个数的和，也就是它们乘积中 $2$ 的个数，即

       $num=n+v_2(1 \times 2 \times 3 \times \cdots \times m-1))=n+v_2((m-1)!)$

       此时可以计算。

   • 所以，约分除去的数就是

     $2^{n+v_2((m-1)!)}$

     可用快速幂求出。

   • 最后一步，分子和分母同时乘需要除去的数的乘法逆元，答案就出来了。

3. 注意

   • 注意数据规模，要开 long long，计算 $nm$ 时需要 __int128。
   • 可以 #define int __int128 这时主函数类型要改，且注意输出时要强制转换为 long long（cout<<(long long)(......)<<......），或者写输出函数（因为标准输入输出不支持 __int128），也要注意选择合适的编译器版本。
   • 注意当 $2^n\le m$ 时直接输出 1 1 退出。
   • 注意计算 $2^i$ 时写成 1LL<<i，不写 LL 会炸。

4. 代码

   #include<bits/stdc++.h>
   #define int __int128
   #define ll long long
   using namespace std;
   const int mod=1e6+3;
   int n，m;
   bool check(){
   	int x=1;
   	for(int i=1;i<=n;i++){
   		x=x*2ll;
   		if(x>=m)
   			return false;
   	}
   	return true;
   }
   int qpow(int _n，int _k){
   	int ans=1ll;
   	while(_k) {
   		if(_k&1ll)
   			ans=ans*_n%mod;
   		_n=_n*_n%mod;
   		_k>>=1ll;
   	}
   	return ans;
   }
   int jian(int _a，int _b){
   	return (_a%mod-_b%mod+mod)%mod;
   }
   int getk(int _n){
   	int sum=0;
   	for(int i=1;_n/(1ll<<i)>0;i++){
   		sum+=_n/(1ll<<i);
   	}
   	return sum;
   }
   main(){
   	ll t_n，t_m;
   	cin>>t_n>>t_m;
   	n=t_n;m=t_m;
   	if(check()){
   		cout<<1<<" "<<1<<endl;
   		return 0;
   	}
   	int a=1;
   	for(int i=1;i<=m;i++){
   		a=a*jian(qpow(2，n)，i-1)%mod;
   		if(a==0)break;
   	}
   	int b=qpow(2，n*m);
   	int k1=n;
   	int k2=getk(m-1);
   	int k=k1+k2;
   	int inv_k=qpow(k，mod-2);
   	cout<<(ll)((b*qpow(500002，k)%mod-a*qpow(500002，k)%mod+mod)%mod)<<" "<<(ll)(b*qpow(500002，k)%mod)<<endl;
   	return 0;
   }