题解：CF1210F1 Marek and Matching (easy version)
CatFromMars
·
·
题解
这个做法也能过 Hard Version 的。
根本不会，严肃学习，肃然起敬，该加训了。
考虑用 Hall 定理刻画。对于 S, T 如果没有完美匹配，考虑其中 S' \subseteq S 作为非法的代表元，满足 |S'| - |N(S')| 最大，同时 |S'| 最小。
这样的代表元一定唯一，证明：
如果不唯一，即两个 S_1, S_2 满足上述条件。如果它们无交，那么有 S_1\cup S_2 显然更优，如果它们有交，那么就有 |S_1| - |N(S_1)| = |S_2| - |N(S_2)|, |S_1| - |N(S_1)| + |S_2| - |N(S_2)| = |S_1 \cup S_2| - |N(S_1 \cup S_2)| + |S_1 \cap S_2| - |N(S_1 \cap S_2)|，于是发现要么然 |S_1 \cap S_2| 一样大且更小，要么然两个中必然有一个更大。
设 f[S, T] 为对于 S，N(S) = T 拥有完美匹配的概率，g[S, T] 为对于 S 内部所有点 S 即为非法代表元的概率。
直接转移非常难转移，因为代表元并不具有子结构。于是正难则反，对于 g[S, T] 考虑 S 并不是代表元的情况，对于 f[S, T] 考虑存在代表元的情况。两种讨论其实很类似，都是考虑 S'\subseteq S, T' \subseteq T 中 (S', T') 作为代表元。如果 (S', T') 是 (S, T) 的代表元，那么概率就是 g[S', T']\times f[S - S', T - T']\times no_{S', T - T'}。
解释一下：
转移就是用 $to_{S, T}$ 代表 $S$ 的邻居集 $N(S) = T$ 的概率，减去上面的不合法的概率。枚举子集即可，时间复杂度 $O(3^{2n})$。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 8, Mod = 1e9 + 7;
int p[N + 3][N + 3], n;
int to[(1 << N) + 3][(1 << N) + 3], no[(1 << N) + 3][(1 << N) + 3];
int f[(1 << N) + 3][(1 << N) + 3], g[(1 << N) + 3][(1 << N) + 3];
int popc[(1 << N) + 3];
void upd(int &x, int y) {
x = ((x + y >= Mod) ? (x + y - Mod) : (x + y));
}
int qpow(int n, int m) {
int res = 1;
while(m) {
if(m & 1) res = 1ll * res * n % Mod;
n = 1ll * n * n % Mod;
m >>= 1;
}
return res;
}
int inv100 = qpow(100, Mod - 2);
void init() {
cin >> n;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
cin >> p[i][j],
p[i][j] = 1ll * p[i][j] * inv100 % Mod;
for(int S = 0; S < (1 << n); S++) {
for(int T = 0; T < (1 << n); T++) {
to[S][T] = no[S][T] = 1;
for(int i = 0; i < n; i++) {
int res = 1;
if(!((T >> i) & 1)) continue;
for(int j = 0; j < n; j++)
if((S >> j) & 1)
res = 1ll * res * (Mod + 1 - p[j][i]) % Mod;
to[S][T] = 1ll * to[S][T] * (Mod + 1 - res) % Mod;
}
for(int i = 0; i < n; i++) {
int res = 1;
if(!((S >> i) & 1)) continue;
for(int j = 0; j < n; j++)
if((T >> j) & 1)
res = 1ll * res * (Mod + 1 - p[i][j]) % Mod;
no[S][T] = 1ll * no[S][T] * res % Mod;
}
}
}
for(int S = 0; S < (1 << n); S++)
for(int T = 0; T < (1 << n); T++)
f[S][T] = g[S][T] = 0;
for(int S = 0; S < (1 << n); S++) {
for(int T = 0; T < (1 << n); T++) {
if(!(S + T)) continue;
g[S][T] = f[S][T] = to[S][T];
if(popc[S] <= popc[T]) g[S][T] = 0;
for(int SS = S; ; SS = (SS - 1) & S) {
for(int TT = T; ; TT = (TT - 1) & T) {
if(popc[S] > popc[T] && popc[SS] - popc[TT] >= popc[S] - popc[T])
upd(g[S][T], Mod - 1ll * g[SS][TT] * no[SS][T - TT] % Mod * f[S - SS][T - TT] % Mod);//如果 (SS, TT) 是更加优秀的代表元，减去这部分
if(popc[S] <= popc[T])
upd(f[S][T], Mod - 1ll * g[SS][TT] * no[SS][T - TT] % Mod * f[S - SS][T - TT] % Mod);//存在代表元就减去
if(!TT) break;
}
if(!SS) break;
}
}
}
cout << f[(1 << n) - 1][(1 << n) - 1] << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
for(int i = 0; i < (1 << N); i++)
popc[i] = __builtin_popcount(i);
// int T; cin >> T;
// while(T--)
init();
}
```