详细揭秘如何 \(O(n \cdot 8^n \cdot 2^{2^ n})\) 过 \(n=7\)。
首先考虑假设已知图的形态，怎么判断是否存在完美匹配。
忘掉你学过的 hall 定理，考虑状压。设 \(f_{i, S}\) 表示左部点前 \(i\) 个和右部点集合 \(S\) 是否存在完美匹配。
那么考虑从 \(f_{i-1,S}\) 转移到 \(f_{i,*}\)。不难发现我们进行的操作其实就是，在左边添加点 \(i\)，并在右边添加和 \(i\) 匹配的点。
枚举 \(i\) 的一个邻居 \(j\) 满足 \(j\) 还没被匹配过，即 \(j \not \isin S\)，然后把 \(j\) 加入匹配点的集合。所以
这是容易的。
然后，我们进行 dp of dp。我们直接把 \(f_{i, S}\) 的一行压成一个 \(2^{2^n}\) 状态。我们假设 \(g_{i, T}\) 表示考虑左部前 \(i\) 个点，\(f\) 的状态为 \(T\) 的概率。
转移的时候，我们先枚举和 \(i\) 相连的边集 \(E\)，然后求出恰好这些边存在的概率，即 \(\prod \limits _{(i, j) \isin E} p_{i,j} \prod \limits _ {(i, j) \not \isin E}(1 - p_{i, j})\)。
然后我们再枚举一个右部点的子集，将其作为前 \(i-1\) 个点的匹配集合。
最后我们枚举 \(i\) 的一个出边（要求这个边要在我们先前选的边集中），将这条边的终点作为 \(i\) 的匹配，更新 \(T\)。
那么这道题就做完了。因为要枚举两个集合，以及枚举有效状态 \(T\)，再加上我偷懒用 map 存状态所以会多乘一个 \(\log 2^{2^n}\)，因此复杂度 \(O(n \cdot 8 ^ n\cdot 2^{2^n})\)。
这玩意凭啥能过？
- 关注到对于一个 \(i\)，\(T\) 中的状态一定都是 \(\operatorname{popcount} = i\) 的。所以实际上有用的状态数量是 \(n \choose i\)，峰值是 \({7 \choose 3} = 35\)，比 \(2^n\) 小了不少。
- 事实上我们只从有用的状态转移。打印出 \(n=7,i=4\) 时的有效状态数只有 \(30262\) 种。这下看着对多了！
#include<bits/stdc++.h>
#define endl '\n'
#define N 10
#define MOD 1000000007
using namespace std;
constexpr __uint128_t _1=1;
inline void mul(int &x,int y) {x=1ll*x*y%MOD;}
inline void add(int &x,int y) {x+=y,x-=x>=MOD?MOD:0;}
int n,p[N][N];
map<__uint128_t,int> mp[N];
void solve(int i)
{if(!i)return mp[i][1]=1,(void)0;for(auto [mask,val]:mp[i-1])for(int S=0;S<(1<<n);S++){int m=1; __uint128_t nxt=0;for(int j=0;j<n;j++)mul(m,(S>>j)&1?p[i][j+1]:(MOD+1-p[i][j+1]));for(int T=0;T<(1<<n);T++)for(int j=0;j<n;j++)if((mask>>T&1)&&!(T>>j&1)&&(S>>j&1))nxt|=_1<<(T|(1<<j));if(nxt&&val&&m)add(mp[i][nxt],1ll*val*m%MOD);}cerr<<mp[i].size()<<endl;
}
main()
{scanf("%d",&n);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&p[i][j]);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)p[i][j]=570000004ll*p[i][j]%MOD;for(int i=0;i<=n;i++)solve(i);printf("%d\n",mp[n][_1<<((1<<n)-1)]);return 0;
}