」题解)
F2. Marek and Matching (hard version)
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|]
\]
\(d(S',T\setminus T')\) 是因为需要保证 \(T=N(S)\)，\(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
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]);
}