题意
题目链接
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 */
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/605049.html