CF54C First Digit Law

在概率论中，存在一个被称为本福德定律的悖论：“在许多来源于实际的数据随机数列表中，以数字 $1$ 开头的数出现的频率远高于其它数字作为首位的情况”（这是该定律最简单的表述形式）。 刺猬在 Codeforces 上读到过这个定律后，对此产生了兴趣，并希望深入研究它。他特别关注如下类似问题：有 $N$ 个随机变量，第 $i$ 个随机变量可以取区间 $[L_{i},R_{i}]$ 内的任意整数（该区间内的所有数出现的概率相等）。也就是说，第 $i$ 个量可以等概率地取 $[L_{i},R_{i}]$ 之间的任意整数，其概率均为 $1/(R_{i}-L_{i}+1)$。 刺猬想知道这样一种事件发生的概率：这些值当中至少有 $K\%$ 的数以 $1$ 为首位数字。换句话说，我们考虑这些随机变量的某组确定取值，仅保留每个值的首位数字（即最高有效数字，MSD）。然后统计首位为 $1$ 的次数，如果至少占这些 $N$ 个值的 $K\%$，那么这组数就被称为“好”的。你需要计算这些随机变量的所有可能取值中，得到“好”组的概率。

第一行包含一个整数 $N$，表示随机变量的数量（$1 \leq N \leq 1000$）。接下来的 $N$ 行每行包含一对整数 $L_{i},R_{i}$，分别描述一个随机变量。保证 $1 \leq L_{i} \leq R_{i} \leq 10^{18}$。 最后一行为一个整数 $K$（$0 \leq K \leq 100$）。 输入文件中所有数字均为整数。 请不要在 C++ 中使用 %lld 读写 64 位整数，建议使用 cin（也可以用 %I64d）。

输出所求概率。结果的小数绝对误差或相对误差不超过 $10^{-9}$。

由 ChatGPT 5 翻译