Solution -「洛谷 P3600」随机数生成器

Desciption

Link.

给定一个值域在 $[1,x]$ 的长度为 $n$ 的序列（由随机数构成），求给定一组区间中的最小值的最大值的期望。

Solution

记：

$$ w=\max\{\min\{a_{l_{j}},a_{l_{j}+1},\cdots,a_{r_{j}}\}|j\in[1,q]\} $$

因为我们最后取的是 $\max$，不能直接用全概率公式，转化一下：

$$ E(w)=\sum_{i=0}^{\infty}P(w\ge i)=\sum_{i=0}^{\infty}1-P(w<i) $$

这意味着每一个被询问区间中的最小值都需 $<i$。也就是说，每一个区间至少需要一个 $<i$ 的数。

这对于每一个区间来说概率为 $\frac{i-1}{x}$。又因为区间可能出现相交，所以我们考虑用点去被包含于区间。

当然，一个区间包含另一个区间，这个区间肯定是没有用的。然后把区间按左右端点分别为第一、第二关键字排序。

枚举 $w$，设 $f_{i}$ 表示区间右端点在 $i$ 之前的所有区间满足条件的概率。

$$ f_{i}=\frac{w-1}{x}\times\sum_{j=0}^{i}f_{j}\times(1-\frac{w-1}{x})^{i-j-1} $$

#include <cstdio>

using i64 = long long;

const int MOD = 666623333;
const int MAXN = 2e3 + 5;

int n, x, q, ar[MAXN];
i64 f[MAXN][2], ff[MAXN][2];

void imax ( int& a, const int b ) { a = a < b ? b : a; }
int add ( const int a, const int b, const int p = MOD ) { return a + b < p ? a + b : ( a + b ) % p; }
int sub ( const int a, const int b, const int p = MOD ) { return a - b < 0 ? a - b + p : a - b; }
int mul ( const i64 a, const i64 b, const int p = MOD ) { return a * b % p; }
int cpow ( int bas, int idx = MOD - 2 ) {
    int res = 1;
    while ( idx ) {
        if ( idx & 1 )    res = mul ( res, bas );
        bas = mul ( bas, bas ), idx >>= 1;
    }
    return res % MOD;
}

int main () {
    scanf ( "%d%d%d", &n, &x, &q );
    for ( int i = 1, tmpl, tmpr; i <= q; ++ i )    scanf ( "%d%d", &tmpl, &tmpr ), imax ( ar[tmpr + 1], tmpl );
    for ( int i = 1; i <= n + 1; ++ i )    imax ( ar[i], ar[i - 1] );
    i64 ix = cpow ( x ), ans = 0;
    for ( int i = 1; i <= x; ++ i ) {
        i64 p = mul ( i - 1, ix ) % MOD, ip = cpow ( 1 - p ), s;
        ff[0][0] = ff[0][1] = 1;
        for ( int j = 1; j <= n; ++ j )    ff[j][0] = mul ( ff[j - 1][0], 1 - p ) % MOD, ff[j][1] = mul ( ff[j - 1][1], ip ) % MOD;
        f[0][0] = 0, f[0][1] = 1;
        for ( int j = 1; j <= n; ++ j ) {
            f[j][0] = mul ( mul ( p, sub ( f[j - 1][1], ar[j] ? f[ar[j] - 1][1] : 0 ) ) % MOD, ff[j - 1][0] ) % MOD;
            f[j][1] = add ( mul ( f[j][0], ff[j][1] ) % MOD, f[j - 1][1] ) % MOD;
        }
        s = 0;
        for ( int j = ar[n + 1]; j <= n; ++ j )    s = add ( s, mul ( f[j][0], ff[n - j][0] ) % MOD ) % MOD;
        ans = sub ( add ( ans, 1 ) % MOD, s );
    }
    printf ( "%lld\n", ans % MOD );
    return 0;
}