题解：CF1210F1 Marek and Matching (easy version)
LastKismet
·
·
题解
sol
是一个 O(3^{2n}) 的做法。
考虑霍尔定理，完美匹配要求任意左部点集合 S 满足 |S|\le |N(S)|，N(S) 为与 S 相连的右部点集合。
考虑容斥。考虑对每个不合法状态都设计一个唯一的代表元，以方便容斥。设 f(S,T) 表示 S,T 可以完美匹配的概率，那么就只需要用 T=N(S) 的概率减去其中存在 S'\subset S,T'\subset T\land T'=N(S) 满足 |S'|>|T'| 的概率即可。
考虑对每一种不合法状态确定一对满足上述不合法条件的 S,T 作为代表元，这样容斥时可以直接枚举代表元转移。我们找 |S|-|T| 最大的一对 S,T 使得其余部分可以完美匹配即可，如果有多种，选择 |S| 最小的。这样的一对 S,T 必然是唯一的。有证明：
假如存在两对 S,T 上面两个条件均相等，分类讨论：
- 若 S_1,S_2 无交，那么 S_1\cup S_2,T1\cup T2 显然不劣。
- 若 S_1,S_2 有交，那么 S_1\cap S_2 或 S_1\cup S_2 不劣。因为 |S_1|-|T_1|+|S_2|-|T_2|\\=|S1\cup S2|-|T_1\cup T_2|+|S_1\cap S_2|-|N(S_1\cap S_2)|\\\le|S1\cup S2|-|T_1\cup T_2|+|S_1\cap S_2|-|T1\cap T2| 如果取等那么取交 |S| 更小，否则必有一个更优。
因此考虑设 g(S,T) 为只考虑 S,T 导出子图时 S,T 为代表元的情况，容斥掉存在更小代表元的情况即可。注意仍需满足 T=N(S)。记 c(S,T) 为 T=N(S) 的概率，d(S,T) 为 S,T 无连边的概率。有转移式：
g(S,T)=c(S,T)-\sum_{S'\subset S}\sum_{T'\subset T}g(S',T')d(S',T\setminus T')f(S\setminus S',T\setminus T')[|S'|-|T'|\ge |S|-|T|]
然后考虑转移 $f$，基本同理，就不额外解释各项意义了：
$$
f(S,T)=c(S,T)-\sum_{S'\subset S}\sum_{T'\subset T}g(S',T')d(S',T\setminus T')f(S\setminus S',T\setminus T')
$$
## code
```cpp
int n;
mint p[N][N],c[1<<N][1<<N],d[1<<N][1<<N],f[1<<N][1<<N],g[1<<N][1<<N];
#define popc(s) __builtin_popcount(s)
inline void Main(){
cin>>n;
repl(i,0,n)repl(j,0,n)cin>>p[i][j],p[i][j]/=100;
repl(s,0,1<<n)repl(t,0,1<<n){
c[s][t]=d[s][t]=1;
if(!s)continue;
repl(j,0,n)if(t>>j&1){
mint v=1;repl(i,0,n)if(s>>i&1)v*=1-p[i][j];
c[s][t]*=1-v,d[s][t]*=v;
}
}
repl(s,0,1<<n)repl(t,0,1<<n){
if(popc(s)<=popc(t)){
f[s][t]=c[s][t];
for(int ss=s-1&s;~ss;ss=ss?ss-1&s:-1)for(int tt=t-1&t;~tt;tt=tt?tt-1&t:-1)
f[s][t]-=g[ss][tt]*d[ss][t^tt]*f[s^ss][t^tt];
}else{
g[s][t]=c[s][t];
for(int ss=s-1&s;~ss;ss=ss?ss-1&s:-1)for(int tt=t-1&t;~tt;tt=tt?tt-1&t:-1)
if(popc(ss)-popc(tt)>=popc(s)-popc(t))g[s][t]-=g[ss][tt]*d[ss][t^tt]*f[s^ss][t^tt];
}
}
put(f[(1<<n)-1][(1<<n)-1]);
}
```