题解：CF1210F2 Marek and Matching (hard version)

dyc2022 · 2026-02-23 18:11:00 · 题解

更好的阅读体验

详细揭秘如何 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;
  }