meaning of the title
Sol
An important property: if an interval covers another interval, then the interval is useless (it will not contribute to the maximum value)
First, it's not hard to think of enumerating the final answer \ (x \). At this time, we need to calculate the probability that the maximum value is exactly \ (x \).
It's not easy to find out. We remember that \ (P(x) \) represents the probability of the maximum \ (\ leqslant x \), so the probability of \ (x \) is \ (P(x) - P(x - 1) \)
The calculation probability can be directly defined by: legal scheme / total scheme (\ (x^n \))
Consider how to calculate the legal scheme: we directly enumerate how many points \ (\ leqslant x \) are in the query interval, and set \ (g(j) \) to represent the scheme that selects \ (j \) points \ (\ leqslant x \) and covers all query intervals. Obviously, this can be done without repetition or leakage.
Next, dp directly calculates \ (g[j] \), and sets \ (f[i][j] \) to indicate the number of schemes covering the first \ (I \) positions, putting \ (j \) points, and the number of schemes that \ (I \) positions must put.
\(f[i][j] = \sum_{fr[k] + 1 \leqslant fl[i]} f[k][j - 1]\)
\(fr[i] \) indicates the number of the rightmost interval covering \ (I \) interval, \ (fl[i] \) indicates the number of the leftmost interval covering \ (I \)
Take the monotone stack when transferring
Complexity \ (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)) //No! flag[j] will wa, because the left and right endpoints may be the same
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
*/