codeforces 紫名每日一题 *[1900~2000]

QQ算竞小群754883088

CF54C. First Digit Law

Problem - C - Codeforces

1.1问题

给定 $N$ 个随机变量，每个随机变量的取值范围在区间 $[L_i, R_i]$ 内，且每个数字的出现概率相等。我们需要计算这些随机变量的首位数字为 1 的概率，且要求至少有 $K\%$ 的随机变量的首位数字为 1。

本题与经典的本福德定律（Benford’s Law）相关，该定律指出，在许多实际的随机数列中，以数字 1 开头的数比其他数字开头的数更为常见。因此，问题的关键是如何计算随机变量取值区间内首位数字为 1 的概率，并根据概率的分布来计算“至少 $K\%$”的概率。

1.2 首位数字为 1 的概率

我们首先需要计算给定区间 $[L, R]$ 中，数字的首位数字为 1 的概率。这个概率可以表示为：

$ P_1(L, R) = \frac{\text{区间内首位数字为 1 的数字数}}{\text{区间内总数字数}} $

计算方法：

为了计算首位数字为 1 的数量，我们将区间 $[L, R]$ 划分为多个包含数字 1 作为首位数字的子区间。每当我们遇到一个新的十进制范围（例如从 1 到 9，10 到 99，等等），我们就检查该范围内有多少数字以 1 为首位数字。通过这种方式，我们可以逐步累加所有符合条件的数字。

1.3 动态规划计算至少 $K\%$ 的概率

由于我们需要计算“至少有 $K\%$ 的随机变量首位数字为 1”的概率，这实际上是一个经典的“多重概率”问题，适合使用动态规划来求解。

1.3.1 状态定义

我们定义一个动态规划数组 $dp[i][j]$，表示在前 $i$ 个随机变量中，有 $j$ 个随机变量的首位数字为 1 的概率。

• 初始状态：$dp[0][0] = 1$，表示没有任何随机变量时，首位数字为 1 的数量为 0 的概率为 1。
• 状态转移：对于每个变量 $i$：
• 如果第 $i$ 个变量的首位数字为 1，那么我们从 $dp[i-1][j-1]$ 转移到 $dp[i][j]$，概率为 $p_i$。
• 如果第 $i$ 个变量的首位数字不是 1，我们从 $dp[i-1][j]$ 转移到 $dp[i][j]$，概率为 $1 - p_i$。

公式为：

$ dp[i][j] = dp[i-1][j] \times (1 - p_i) + dp[i-1][j-1] \times p_i $

1.3.2 计算最终结果

最终的目标是求出至少有 $K\%$ 的随机变量的首位数字为 1 的概率。假设 $K\%$ 对应的阈值为 $k_{\text{min}} = \lceil \frac{K \times N}{100} \rceil$，我们需要计算 $dp[N][j]$ 对应于所有 $j \geq k_{\text{min}}$ 的概率之和：

$ \text{答案} = \sum_{j=k_{\text{min}}}^{N} dp[N][j] $

2. 解法思路

2.1 计算每个随机变量的首位数字为 1 的概率

对于每个随机变量 $i$ 所对应的区间 $[L_i, R_i]$，我们可以按照上述方法计算其首位数字为 1 的概率 $p_i$。

2.2 动态规划求解

根据动态规划的转移公式，最终通过累加所有符合条件的概率 $dp[N][j]$ 来得到最终的结果。

2.3 代码

// Codeforces - Codeforces Beta Round 50 C. First Digit Law
// https://codeforces.com/contest/54/problem/C 2024-11-27 14:27:31

#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a), end(a)
#define int long long
#define debug(x) cout << #x << " = " << x << "\n"
int n, k;
using ld = long double;
void solve() {
  cin >> n;
  vector<int> L(n), R(n);
  vector<ld> p(n);
  for (int i = 0; i < n; i++) {
    __int128 l, r;
    int l1, r1;
    cin >> l1 >> r1;
    l = l1, r = r1;
    __int128 st = 1;
    int res = 0;
    while (st <= r) {
      __int128 ed = st + st - 1;
      if (min(r, ed) >= max(st, l)) {
        res += min(r, ed) - max(st, l) + 1;
      }
      st *= 10;
    }
    p[i] = (res * 1.) / (r - l + 1);
  }
  p.insert(p.begin(), 0LL);
  vector dp(n + 1, vector<ld>(n + 1));
  dp[0][0] = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= n; j++) {
      dp[i][j] = dp[i - 1][j] * (1. - p[i]);
      if (j) {
        dp[i][j] += dp[i - 1][j - 1] * p[i];
      }
    }
  }
  cin >> k;
  ld ans = 0;
  for (int j = 0; j <= n; j++)
    if (j * 100. / n >= k) ans += dp[n][j];
  cout << ans << "\n";
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  cout << fixed << setprecision(15);
  solve();
  return 0;
}