最近報了航電的春季賽，在一道題目里面遇到了做法，感覺挺有意思。

考慮一個（多重）集合S={ai}S=\{a_i\}S={ai?}，有如下的等式成立

$$\underset{a_i\in S}{\min }(a_i)=\sum _{T?S,T\ne ?}(?1{)}^{|T|?1}\underset{a_i\in T}{\max }(a_i)$$

反之亦然，

$$\underset{a_i\in S}{\max }(a_i)=\sum _{T?S,T\ne ?}(?1{)}^{|T|?1}\underset{a_i\in T}{\min }(a_i)$$

這兩個公式還是比較容易理解的，這里只拿第一條式子進行分析。

首先是最小的元素$a_1$，只有T={a1}T=\{a_1\}T={a1?}的時候才有$a_1$的貢獻。

對于其它的元素，假設有$k$個比它小的數，那么這個元素總的貢獻就是${\sum }_{i=0}^k(?1{)}^i{C}_k^i=(1?1{)}^k=0$，因此這么容斥下來就會得到最小的數。

回到這一題中，因為有期望，所以這兩個式子不能直接用。但因為期望實際上把全部情況加起來，因此可以直接把兩邊加上期望，即

$$E(\underset{a_i\in S}{\min }(a_i))=E(\sum _{T?S,T\ne ?}(?1{)}^{|T|?1}\underset{a_i\in T}{\max }(a_i))$$

在這一題中，集合就是沒有被污染的行和列，而max操作就意味著要把集合行和列全部染上。

考慮一共有$x$個點在選出來的行和列里面，嘗試計算把全部點染完的期望步數。首先，染完第一個點的概率是$\frac{x}{n\times m}$，因此期望步數為$\frac{n\times m}{x}$；在此之后，染完第二個點的概率是$\frac{x?1}{n\times m}$，因此期望步數為$\frac{n\times m}{x?1}$，因此類推，總的貢獻就是${\sum }_{i=1}^k\frac{n\times m}{i}$。

#include <bits/stdc++.h>
#define ll long long
using namespace std;const int N = 1e6 + 10, mod = 998244353;int power(int a, int b) {int ret = 1;while (b) {if (b & 1) ret = 1ll * ret * a % mod;a = 1ll * a * a % mod; b >>= 1;}return ret;
}int n, m, k;
vector<int> a[N];
int f[N];
int fc[N], ifc[N];int C(int a, int b) {return 1ll * fc[a] * ifc[b] % mod * ifc[a - b] % mod;
}void solve() {cin >> n >> m >> k;f[1] = 1;for (int i = 2; i <= n * m; i++) {f[i] = (f[i - 1] + power(i, mod - 2)) % mod;}fc[0] = 1;for (int i = 1; i <= n * m; i++) {fc[i] = 1ll * fc[i - 1] * i % mod;}ifc[n * m] = power(fc[n * m], mod - 2);for (int i = n * m - 1; i >= 0; i--) {ifc[i] = 1ll * ifc[i + 1] * (i + 1) % mod;}for (int i = 1; i <= n; i++) {a[i].clear();a[i].resize(m + 5);}for (int i = 1; i <= k; i++) {int x, y;cin >> x >> y;a[x][y] = 1;}int s1 = 0, s2 = 0;for (int i = 1; i <= n; i++) {bool bk = 1;for (int j = 1; j <= m; j++) {if (a[i][j]) {bk = 0; break;}}if (bk) s1++;}for (int i = 1; i <= m; i++) {bool bk = 1;for (int j = 1; j <= n; j++) {if (a[j][i]) {bk = 0; break;}}if (bk) s2++;}if (!s1 && !s2) {cout << "-1\n";return;}int ans = 0;for (int i = 0; i <= s1; i++) {for (int j = 0; j <= s2; j++) {if (!i && !j) continue;int w = (i + j) % 2 ? 1 : mod - 1;int cnt = i * m + j * n - i * j;int ret = 1ll * n * m * f[cnt] % mod;ret = 1ll * ret * C(s1, i) % mod * C(s2, j) % mod;ret = 1ll * ret * w % mod;ans = (ans + ret) % mod;}}cout << ans << endl;
}int main() {// freopen("in.in", "r", stdin);ios::sync_with_stdio(false);cin.tie(nullptr);int T; cin >> T;while (T--) solve();return 0;
}

下一題是[HAOI2015] 按位或

設$S$是每一位的集合

根據前面所說的公式

$$E(\max (S))=\sum _{T?S,T\ne ?}E(\min (T))$$

也就是要枚舉每一個子集，求出其第一個出現期望有多久。

我們只需要用高維前綴和算出選擇一次不包括$T$的概率$p$，那么$E(\min (T))=\frac{1}{1?p}$，然后就可以求出$E(\max (S))$了。

#include <bits/stdc++.h>
#define ll long long
using namespace std;const int N = (1 << 20) + 10;
const double eps = 1e-9;int n; double f[N], g[N];int main() {// freopen("in.in", "r", stdin);ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n;for (int i = 0; i < (1 << n); i++) {cin >> f[i];g[i] = f[i];}for (int j = 0; j < n; j++) {bool flag = 0;for (int i = 0; i < (1 << n); i++) {if (i >> j & 1) {if (f[i] > eps) {flag = 1; break;}}}if (!flag) {cout << "INF\n";return 0;}}for (int j = 0; j < n; j++) {for (int i = 0; i < (1 << n); i++) {if (i >> j & 1) {g[i] += g[i - (1 << j)];}}}double ans = 0;for (int i = 1; i < (1 << n); i++) {double w = -1;for (int j = 0; j < n; j++) {if (i >> j & 1) w = -w;}int mask = ((1 << n) - 1) ^ i;double t = 1.0 / (1.0 - g[mask]);ans += w * t;}cout << fixed << setprecision(8) << ans << endl;
}