CF54C First Digit Law Solution

今日は確率dpの問題全体をテーマリンク(luogu)codeforcesにします
テーマの大意
数n n n nを与え、n n n行、各行l i l_を与えるi li​, r i r_i riは、i番目のi個の数を表す区間[l i,r i][l_i,r_i][li,ri]において、このn n個の数のうちk k%の数が1 1 1 1で始まるように確率を求める.
テーマの考え方
ああ、この確率を見ると、あの暗い時間を思い出して咳をして、本題に戻ってまずこの区間[l,r][l,r][l,r]の間の数について、差分でそれらの冒頭が1 1 1である確率を求めることができます.各区間の寄与を考慮して,最後に暴力列挙[1,n][1,n][1,n][1,n]を加算して条件を満たす確率を求めればよい.
コード#コード#
具体的な実装はコードを参照

typedef long long ll;
ll count(ll n)
{
    ll ans = 0, x = 1, cnt = 0, high = 0, num = n;
    while (num)
    {
        high = num % 10;
        num /= 10;
        cnt++;
    }
    cnt--;
    for (int i = 1; i <= cnt; i++, x *= 10)
        ans += x;
    if (high > 1)
        ans += x;
    else if (high == 1)
        ans += n - x + 1;
    return ans;
}
const int N = 1005;
double p[N], dp[N], ans;
int n, k;
ll l, r;
int main()
{
    ios :: sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> l >> r;
        ll tmp = count(r) - count(l - 1);
        p[i] = 1.0 * tmp / (r - l + 1);
    }
    cin >> k;
    dp[0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = n; j >= 0; j--)
        {
            dp[j] = dp[j] * (1 - p[i]);//      
            if (j > 0)
                dp[j] += dp[j - 1] * p[i];
        }
    for (int i = 0; i <= n; i++)
        if (i * 100 >= n * k)
            ans += dp[i];
    printf ("%.15f", ans);
    return 0;
}

ありがとう