Luckyleaves's Blog

stay hungry，stay foolish greedy and lucky

CF54C First Digit Law

Posted on Edited on

比较强的一种Dp板题。

Solution

首先将所有区间的概率算出来，显然有方程：
$$
f_{i,j}=(1-a_i)f_{i-1,j}+a_if_{i-1,j-1}
$$
这样就可以做到$O(n^2)$。

考虑优化，设每个点的生成函数为$1-a_i+a_ix$，$x$的次幂就表示选了几个，分治$NTT$就可以做到$O(n\log^2n)$。

Code

这是$O(n^2)$的，毕竟$n$只有$1000$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<bits/stdc++.h>
#define PII pair<int, int>
#define LL long long
using namespace std;
template <class T>
inline void read(T &res)
{
	res = 0; bool flag = 0;
	char c = getchar();
	while(c < '0' || '9' < c) {if(c == '-') flag = 1; c = getchar();}
	while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
	if(flag) res = -res; 
}
template <class T, class ...ARC>
inline void read(T &res, ARC &...com){ read(res), read(com...); }
template <class T>
void write(T res)
{
	if(res < 0) putchar('-'), res = -res;
	if(res > 9) write(res / 10);
	putchar(res % 10 + '0');
}
template <>
inline void write(char c) { putchar(c); }
template <>
inline void write(char *s) { while(*s) putchar(*s ++);}
template <class T, class ...ARC>
inline void write(T res, ARC ...com) { write(res), write(com...); } 
const int N = 1005;
int n, m, id[N], cnt;
double a[N];
double f[N][N];
LL dp[20][2][2];
LL dfs(int x, int type, int flag, int p)
{
    if(x == 0) return flag;
    if(!type && dp[x][flag][p] != -1) return dp[x][flag][p];
    int up = type ? id[x] : 9;
    LL res = 0;
    for(int i = 0;i <= up;i ++)
        res += dfs(x - 1, type & (i == up), flag | ((i == 1) && !p), p | (i != 0));
    if(!type) dp[x][flag][p] = res;
    return res;
}
inline LL calc(LL x)
{
    memset(dp, -1, sizeof(dp));
    cnt = 0;
    while(x) id[++ cnt] = x % 10, x /= 10;
    return dfs(cnt, 1, 0, 0);
}
int main()
{
    read(n);
    for(int i = 1;i <= n;i ++)
    {
        LL l, r;
        read(l, r);
        a[i] = (calc(r) - calc(l - 1)) / (r - l + 1.);
    }
    f[0][0] = 1;
    for(int i = 1;i <= n;i ++)
    {
        f[i][0] = f[i - 1][0] * (1.0 - a[i]);
        for(int j = 1;j <= n;j ++)
            f[i][j] = f[i - 1][j - 1] * a[i] + f[i - 1][j] * (1.0 - a[i]);
    }
    double ans = 0;
    read(m);
    m = ceil((double)n * m / 100);
    for(int i = m;i <= n;i ++) ans += f[n][i];
    printf("%.12lf", ans);
    return 0;
}