洛谷P3600 随机数生成器(期望dp 组合数)

题意

题目链接

sol

一条重要的性质：如果某个区间覆盖了另一个区间，那么该区间是没有用的(不会对最大值做出贡献)

首先不难想到枚举最终的答案\(x\)。这时我们需要计算的是最大值恰好为\(x\)的概率。

发现不是很好搞，我们记\(p(x)\)表示最大值\(\leqslant x\)的概率，那么恰好为\(x\)的概率为\(p(x) - p(x - 1)\)

计算概率可以直接用定义：合法的方案/总方案(\(x^n\))

考虑如何计算合法方案：我们直接去枚举在询问区间中有多少个点\(\leqslant x\)，设\(g(j)\)表示选出\(j\)个\(\leqslant x\)的点且覆盖了所有询问区间的方案，显然这样可以做到不重不漏。

接下来直接dp计算\(g[j]\)，设\(f[i][j]\)表示覆盖了前\(i\)个位置，放了\(j\)个点的方案数，且\(i\)位置必须放的方案数。

\(f[i][j] = \sum_{fr[k] + 1 \leqslant fl[i]} f[k][j - 1]\)

\(fr[i]\)表示覆盖了\(i\)区间的最右区间的编号，\(fl[i]\)表示覆盖了\(i\)的最左区间的编号

转移的时候拿单调栈搞一下

复杂度\(o(n^2 logn)\)

#include<bits/stdc++.h> 
#define pair pair<ll, ll>
#define mp(x, y) make_pair(x, y)
#define fi first
#define se second
#define ll long long 
#define fin(x) {freopen(#x".in","r",stdin);}
#define fout(x) {freopen(#x".out","w",stdout);}
using namespace std;
const int maxn = 2001, mod =666623333, inf = 1e9 + 10;
const double eps = 1e-9;
template <typename a, typename b> inline bool chmin(a &a, b b){if(a > b) {a = b; return 1;} return 0;}
template <typename a, typename b> inline bool chmax(a &a, b b){if(a < b) {a = b; return 1;} return 0;}
template <typename a, typename b> inline ll add(a x, b y) {if(x + y < 0) return x + y + mod; return x + y >= mod ? x + y - mod : x + y;}
template <typename a, typename b> inline void add2(a &x, b y) {if(x + y < 0) x = x + y + mod; else x = (x + y >= mod ? x + y - mod : x + y);}
template <typename a, typename b> inline ll mul(a x, b y) {return 1ll * x * y % mod;}
template <typename a, typename b> inline void mul2(a &x, b y) {x = (1ll * x * y % mod + mod) % mod;}
template <typename a> inline void debug(a a){cout << a << '\n';}
template <typename a> inline ll sqr(a x){return 1ll * x * x;}
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, x, q, flag[maxn], fl[maxn], fr[maxn], g[maxn], cnt, tmp[maxn], f[maxn][maxn], que[maxn], top, sum[maxn];
int fp(int a, int p) {
    int base = 1;
    while(p) {
        if(p & 1) base = mul(base, a);
        a = mul(a, a); p >>= 1;
    }
    return base;
}
int inv(int x) {
    return fp(x, mod - 2);
}
int solve(int x) {//find the probability that max <= x
    int now = 0;
    for(int i = 1; i <= n; i++) add2(now, mul(g[i], mul(fp(x, i), fp(x - x, n - i))));//choose j point staticfiac
    return mul(now, inv(fp(x, n)));
}
pair q[maxn];
signed main() {
    fin(a);
    n = read(); x = read(); q = read();
    for(int i = 1; i <= q; i++) q[i].fi = read(), q[i].se = read();
    for(int i = 1; i <= q; i++) 
        for(int j = 1; j <= q; j++) 
            if(!flag[j] && (i != j) && (q[i].fi <= q[j].fi && q[i].se >= q[j].se)) //不加!flag[j]会wa，因为可能左右端点都相同 
                flag[i] = 1;
    for(int i = 1; i <= q; i++) if(!flag[i]) q[++cnt] = q[i];
    q = cnt;
    sort(q + 1, q + q + 1);
    memset(fl, 0x3f, sizeof(fl));
    for(int i = 1; i <= q; i++)
        for(int j = 1; j <= n; j++)
            if(q[i].fi <= j && q[i].se >= j) chmin(fl[j], i), chmax(fr[j], i);
            else if(q[i].se < j) chmax(fr[j], i);
    for(int i = 1; i <= n; i++) if(q[fr[i]].se < i) fl[i] = fr[i] + 1;

    /*
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= min(i, n); j++)
            for(int k = 0; k < i; k++)
                if(fr[k] + 1 >= fl[i]) add2(f[i][j], f[k][j - 1]);
    */
    f[0][0] = 1;
    int l = 1, r = 1; que[1] = 0; sum[0] = 1;
    for(int i = 1; i <= n; i++) {
        while(l <= r && fr[que[l]] + 1 < fl[i]) {
            for(int j = 0; j <= n; j++) 
                add2(sum[j], -f[que[l]][j]);
            l++;
        }
        for(int j = 1; j <= min(i, n); j++) f[i][j] = sum[j - 1];
        for(int j = 1; j <= n; j++) add2(sum[j], f[i][j]);
        que[++r] = i;
    }
    for(int i = 1; i <= n; i++)
        if(fr[i] == q)
            for(int j = 1; j <= n; j++)
                add2(g[j], f[i][j]);
    ll ans = 0;
    for(int i = 1; i <= n; i++) tmp[i] = solve(i);
    for(int i = 1; i <= x; i++) add2(ans, mul(i, add(tmp[i], -tmp[i - 1])));
    cout << ans;
    return 0;
}
/*
32 4
*/