Marek and Matching (hard version)
非常好 trick，我又没见过。搬运写一下题解。
二分图完美匹配直接考虑 Hall 定理，Hall 定理的内容要求 \(\forall S,|S|\le |N(S)|\)，这个 \(\forall\) 非常不好，于是正难则反，计算不合法方案，但是这个不合法方案看着就很容易算重，然后你如果去考虑用 \(ans=\sum (-1)^res(i)\)（\(res(i)\) 表示有 \(i\) 个 \(S\) 满足 \(|S|>|N(S)|\) 的概率）计算答案基本就废了，这题我们要考虑换一个思路。
我们考虑对每一个不合法情况（也就是没有完美匹配）钦定一个代表元，这题中我们钦定 \(|S|-|N(S)|\) 最大的 \((S,N(S))\) 为代表元（相同取 \(|S|\) 小的），下面我们证明对于一个不合法情况，代表元 \(S\) 是唯一确定的。
假设同时存在最优的 \(S,T\)，\(|S|-|N(S)|=|T|-|N(T)|,|S|=|T|,S\ne T\)，那么注意到：
于是 \(S\cup T,S\cap T\) 中必有一个更优的。
于是我们就可以 DP 了，设 \(f_{S,T}\) 表示 \(S,T\) 之间有完美匹配的概率，\(g_{S,T}\) 表示 \(S,T\) 之间没有完美匹配且 \((S,T)\) 是代表元的概率，\(no_{S,T}\) 表示 \(S,T\) 之间没有边的概率，\(out_{S,T}\) 表示 \(N(S)=T\) 的概率。（以上定义均只考虑 \(S,T\) 之间的边，其他边的概率都不考虑），转移：
解释一下 \(g\) 的转移，\(f\) 类似：容斥，减去代表元不是 \((S,T)\) 的概率，\(f_{S/S',T/T'}\) 是因为如果 \(S/S',T/T'\) 之间没有完美匹配，那么 \((S',T')\) 并上 \(S/S',T/T'\) 的代表元会更优，\(no_{S',T/T'}\) 是为了保证 \(N(S')=T'\)。
复杂度 \(O(3^{2n})\)。
#include<bits/stdc++.h>
#define Debug cerr<<"-----------------------------------"<<'\n'
using namespace std;
const int N=(1<<8)+5,mod=1e9+7;
int qp(int a,int b){int ans=1;while(b){if(b&1) ans=1ll*ans*a%mod;b>>=1,a=1ll*a*a%mod; } return ans;
}
int n,p[10][10],siz[N],no[N][N],out[N][N],f[N][N],g[N][N];
void Init(){for(int S=0;S<(1<<n);S++){siz[S]=__builtin_popcount(S);for(int T=0;T<(1<<n);T++){int ans1=1,ans2=1;for(int j=0;j<n;j++){if(!(T>>j&1)) continue;int P=1;for(int i=0;i<n;i++){if(!(S>>i&1)) continue;ans1=1ll*ans1*(1-p[i+1][j+1]+mod)%mod;P=1ll*P*(1-p[i+1][j+1]+mod)%mod; }P=(1-P+mod)%mod;ans2=1ll*ans2*P%mod; }no[S][T]=ans1,out[S][T]=ans2;}}
}
signed main(){
// freopen("binary.in","r",stdin);
// freopen("binary.out","w",stdout);double beg=clock();scanf("%d",&n);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){scanf("%d",&p[i][j]); p[i][j]=1ll*p[i][j]*qp(100,mod-2)%mod;}}Init(); for(int S=1;S<(1<<n);S++){for(int T=0;T<(1<<n);T++){if(siz[T]<siz[S]){g[S][T]=out[S][T];for(int S1=S;S1;S1=(S1-1)&S){for(int T1=T;;T1=(T1-1)&T){if((S!=S1||T!=T1)&&(siz[S1]-siz[T1]>=siz[S]-siz[T])){(g[S][T]+=mod-1ll*g[S1][T1]*f[S^S1][T^T1]%mod*no[S1][T^T1]%mod)%=mod;}if(!T1) break;}}}f[S][T]=out[S][T];for(int S1=S;S1;S1=(S1-1)&S){for(int T1=T;;T1=(T1-1)&T){(f[S][T]+=mod-1ll*g[S1][T1]*f[S^S1][T^T1]%mod*no[S1][T^T1]%mod)%=mod;if(!T1) break;}} }}printf("%d\n",f[(1<<n)-1][(1<<n)-1]);cerr<<"Times : "<<(clock()-beg)<<"ms"<<'\n';return 0;
}