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…