好久没复习过 min-max 容斥了……
设 \(i\) 被覆盖的时间为 \(t_i\),考虑 min-max 容斥,那么:
\[E(\max\limits_{i \in S} t_i) = \sum\limits_{T \subseteq S \land T \ne \varnothing} (-1)^{|T| - 1} E(\min\limits_{i \in T} t_i)
\]
\(\min\) 是好做的。设有 \(x\) 条线段与 \(T\) 有交,那么 \(E(\min\limits_{i \in T} t_i) = \frac{m}{x}\)。
考虑直接 dp,并且把 \(x\) 塞进状态里。设 \(f_{i, j}\) 表示考虑了 \([1, i]\),钦定 \(i\) 被选,已经有 \(j\) 条线段与 \(T\) 无交的方案数,把容斥系数 \((-1)^{|T| - 1}\) 塞进转移里即可。
时间复杂度 \(O(n^2m)\)。
code
// Problem: Ex - Random Painting
// Contest: AtCoder - AtCoder Beginner Contest 242
// URL: https://atcoder.jp/contests/abc242/tasks/abc242_h
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 410;
const ll mod = 998244353;
inline ll qpow(ll b, ll p) {
ll res = 1;
while (p) {
if (p & 1) {
res = res * b % mod;
}
b = b * b % mod;
p >>= 1;
}
return res;
}
ll n, m, f[maxn][maxn], g[maxn][maxn], h[maxn];
struct node {
ll l, r;
} a[maxn];
void solve() {
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= m; ++i) {
scanf("%lld%lld", &a[i].l, &a[i].r);
++g[a[i].l][a[i].r];
}
for (int i = n; i; --i) {
for (int j = 1; j <= n; ++j) {
g[i][j] += g[i + 1][j] + g[i][j - 1] - g[i + 1][j - 1];
}
}
f[0][0] = mod - 1;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
for (int k = 0; k < i; ++k) {
if (j >= g[k + 1][i - 1]) {
f[i][j] = (f[i][j] - f[k][j - g[k + 1][i - 1]] + mod) % mod;
}
}
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
if (j >= g[i + 1][n]) {
h[m - j] = (h[m - j] + f[i][j - g[i + 1][n]]) % mod;
}
}
}
ll ans = 0;
for (int i = 1; i <= m; ++i) {
ans = (ans + m * qpow(i, mod - 2) % mod * h[i] % mod) % mod;
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Beginner Painting AtCoder Contest Randombeginner painting atcoder contest beginner atcoder contest random beginner painting weighted atcoder contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 334