YZOJ P4621 [CSP-S 2019 四校联训 Round 1]生日悖论

时间限制：1000MS      内存限制：131072KB

难度：\(5.0\)

• 题目描述

一共有 \(N\) 种数字，所以按照包含数字的集合分类，可能有 \(2^N\) 类不同的集合。每个集合包含一种特定的数字的概率都是 \(\displaystyle\frac{1}{2}\) 。

随机取其中 \(k\) 个集合，请你帮忙算一下其中存在两个集合完全相同的概率。

• 输入格式

一行两个整数 \(N,k\) 。

• 输出格式

两个正整数，分别表示概率（最简分数）的分子和分母。分别对 \(10^6+3\) 取模吧。

• 数据规模与约定

\(1 \leq N \leq 10^{18}\)，\(2 \leq k \leq 10^{18}\) 。

 

 

Source： CodeForces 711E ZS and The Birthday Paradox

---

 

 

 

若 \(2^N<K\) ，答案为 \(1\) 。

否则答案为 \(\displaystyle 1- \frac{P_{2^N}^{K}}{{2^N}^K}\) 。

发现这两的 \(\gcd\) 肯定是 \(2\) 的某个次幂，并且分母中因子 \(2\) 的个数肯定比分子多。

同时约掉 \(2^N\)，要在分子 \(\displaystyle\frac{P_{2^N}^{K}}{2^N} = (2^N-1)(2^N-2)\cdots(2^N-K+1)\) 中找出因子 \(2\) 的个数。

注意到 \(\left|-K+1\right|\) 中因子 \(2\) 的个数肯定比 \(2^N\) 少，所以只需要找出 \(1, 2, \cdots, K-1\) 中每个数各包含因子 \(2\) 的个数。

为 \(\displaystyle \left\lfloor\frac{K-1}{2}\right\rfloor + \left\lfloor\frac{K-1}{4}\right\rfloor + \cdots + \left\lfloor\frac{K-1}{2^i}\right\rfloor\)，其中 \(i\) 为满足 \(2^i \leq K-1\) 最大的整数。

这样 \(\gcd\) 和分母就解决了，剩下分子还没算出来。

根据抽屉原理，若 \(K-1 \geq MOD\) 则连续的 \(K-1\) 个数乘积一定包含 \(MOD\) 的倍数，即分子为 \(0\) ；

否则因为 \(MOD\) 比较小，暴力算即可。

最后逆元算一下即可。