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

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\) 比较小,暴力算即可。

最后逆元算一下即可。

 

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注