Cf 54C First Digit Law

Cf 54C First Digit Law

题意:

一个数组中有n个数，给出第 \(i\) 个数的范围 \([l_i,r_i]\) ，定义这n个数中以1开头的数为特殊数，求这n个数中，特殊的数出现的比例至少为k%的概率。

数据范围:

$ 1 \le n \le 1000, 1\le L_i \le R_i \le 10^{18} , 0 \le k \le100 $

思路:

定义dp[i][j]为到第 \(i\) 个数，出现 \(j\) 个特殊数的概率。

dp[i][j] = 当前数是特殊数的概率*dp[i - 1][j - 1] + 当前数不是特殊数的概率*dp[i - 1][j]。

当 $j = 0 $ 的时候需要特殊处理,dp[i][0] = 当前数不是特殊数的概率 * dp[I - 1][0]

实现:

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1005;
double l[N], r[N];
int query(unsigned long long l, unsigned long long r)
{
    if (l > r)
        swap(l, r);
    unsigned long long t = 1, ret = 0;
    while (t <= l)
        t *= 10;
    t /= 10;

    while (l <= r)
    {
        if (l / t < 2)
        {
            if (2 * t <= r)
                ret += 2 * t - l;
            else
                ret += (r - l + 1);
        }
        t *= 10;
        l = t;
    }
    return ret;
}
int n;
double f[N][N];
double dp[N];
signed main()
{
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lf%lf", &l[i], &r[i]);

    f[0][0] = 1;
    int k;
    scanf("%lld", &k);

    for (int i = 1; i <= n; i++)
    {
        double prob = query(l[i], r[i]) * 1.0 / (r[i] - l[i] + 1);
        f[i][0] = f[i - 1][0] * (1 - prob);
        for (int j = 1; j <= i; j++)
            f[i][j] = f[i - 1][j - 1] * prob + f[i - 1][j] * (1 - prob);
    }
    double res = 0;
    for (int i = n; 100 * i >= n * k; i--)
        res += f[n][i];
    printf("%.10f", res);
    return 0;
}