Processing math: 3%

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

最后逆元算一下即可。

 

 

 

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注