P14170 二分图最大匹配期望 做题记录

给定 $n,m$ 和一个 $n\times m$ 的非负整数矩阵 $a$，$a_{i,j}\in [0,100]$。

根据这个矩阵构造一个二分图，其有 $n$ 个左部点和 $m$ 个右部点，连接第 $i$ 个左部点和第 $j$ 个右部点的无向边 $(i,j)$ 有 $\frac{a_{i,j}}{100}$ 的概率存在。

求这个二分图的最大匹配大小的期望。

$1\le n,m\le 9$。

考虑 Hall 定理，一个二分图的最大匹配大小为 $n-\max\limits_{S}\left(|S|-|N(S)|\right)$，其中 $N(S)$ 是左部点集 $S$ 的邻域。

问题是取到最大值的 $S$ 可能有多个。

勇敢地去考虑代表元，不妨令代表元为 $|S|-|N(S)|$ 最大且 $|S|$ 最小的左部点集 $S$。可以证明这是唯一的：

若有两个左部点集 $S,T$ 满足 $|S|-|N(S)|=|T|-|N(T)|$ 且 $|S|=|T|$，则：

$|S|-|N(S)|+|T|-|N(T)|\le|S\cap T|-|N(S\cap T)|+|S\cup T|-|N(S\cup T)|$

这是因为 $|S|+|T|=|S\cap T|+|S\cup T|$ 且 $|N(S)|+|N(T)|\ge|N(S\cap T)|+|N(S\cup T)|$。

那么 $S\cap T$ 和 $S\cup T$ 中的某一个集合一定能优于 $S$ 和 $T$，矛盾。

那么就可以 dp 了，设 $g_{S,T}$ 表示只考虑左部点集 $S$ 和右部点集 $T$ 的子图时，$N(S)=T$ 且 $S$ 是子图代表元的概率；$f_{S,T}$ 表示只考虑 $S,T$ 的子图时，$N(S)=T$ 且最大匹配大小为 $|S|$ 的概率。

转移考虑容斥，枚举实际的代表元 $S'$，那么 $S-S'$ 和 $T-N(S')$ 的导出子图的最大匹配大小显然为 $|S-S'|$，故有转移：

$f_{S,T}=h_{S,T}-\sum\limits_{S'\subseteq S,T'\subseteq T,|S'|+|T'|\not=0} g_{S',T'}\times f_{S-S',T-T'}\times noe_{S',T-T'}\\ g_{S,T}=h_{S,T}-\sum\limits_{S'\subseteq S,T'\subseteq T,|S'|+|T'|\not=|S|+|T|,|S'|-|T'|\ge |S|-|T|} g_{S',T'}\times f_{S-S',T-T'}\times noe_{S',T-T'}$

其中 $h_{S,T}$ 表示只考虑 $S,T$ 的子图时 $N(S)=T$ 的概率，$noe_{S,T}$ 表示 $S,T$ 之间没有边的概率。

计算答案是简单的，枚举整个图的代表元 $S$ 和 $N(\{1,2,3,\dots ,n\}-S)$ 即可。

时间复杂度 $O(3^{n+m})$，代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

#define p 998244353

inline void add(int &x,int y)
{
	x+=y;
	if(x>=p) x-=p;
}
inline int qpow(int x,int y)
{
	int res=1;
	for(;y>0;y>>=1,x=1ll*x*x%p) res=y&1?1ll*res*x%p:res;
	return res;
}

const int S=15,BS=1<<9;

int n,m,a[S][S];
int noe[BS][BS],h[BS][BS],f[BS][BS],g[BS][BS];

#define popc(x) __builtin_popcount(x)

inline void slove()
{
	cin>>n>>m;
	int iv=qpow(100,p-2);
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			cin>>a[i][j],a[i][j]=1ll*a[i][j]*iv%p;
	for(int s=0;s<(1<<n);s++)
		for(int t=0;t<(1<<m);t++)
			noe[s][t]=h[s][t]=f[s][t]=g[s][t]=0;
	for(int s=0;s<(1<<n);s++)
		for(int t=0;t<(1<<m);t++)
		{
			noe[s][t]=1;
			for(int i=0;i<n;i++)
				for(int j=0;j<m;j++)
					if((s>>i&1)&&(t>>j&1))
						noe[s][t]=1ll*noe[s][t]*(1-a[i][j]+p)%p;
		}
	for(int s=0;s<(1<<n);s++)
		for(int t=0;t<(1<<m);t++)
		{
			h[s][t]=1;
			for(int j=0;j<m;j++)
			{
				if(t>>j&1^1) continue;
				int pre=1;
				for(int i=0;i<n;i++)
					if(s>>i&1) pre=1ll*pre*(1-a[i][j]+p)%p;
				h[s][t]=1ll*h[s][t]*(1-pre+p)%p;
			}
		}
	for(int s=0;s<(1<<n);s++)
		for(int t=0;t<(1<<m);t++)
			if(popc(s)<=popc(t))
			{
				f[s][t]=h[s][t];
				for(int s1=s;;s1=(s1-1)&s)
				{
					for(int t1=t;;t1=(t1-1)&t)
					{
						if(s1!=0||t1!=0)
							add(f[s][t],p-1ll*g[s1][t1]*f[s-s1][t-t1]%p
									*noe[s1][t-t1]%p);
						if(t1==0) break;
					}
					if(s1==0) break;
				}
			}
			else
			{
				g[s][t]=h[s][t];
				for(int s1=s;;s1=(s1-1)&s)
				{
					for(int t1=t;;t1=(t1-1)&t)
					{
						if((s1!=s||t1!=t)
							&&popc(s1)-popc(t1)>=popc(s)-popc(t))
						{
							add(g[s][t],p-1ll*g[s1][t1]*f[s-s1][t-t1]%p
									*noe[s1][t-t1]%p);
						}
						if(t1==0) break;
					}
					if(s1==0) break;
				}
			}
	int ans=0;
	int alln=(1<<n)-1,allm=(1<<m)-1;
	for(int s=0;s<(1<<n);s++)
		for(int t=0;t<(1<<m);t++)
			if(popc(s)>popc(t))
			{
				int lst=allm-t;
				for(int x=lst;;x=(x-1)&lst)
				{
					add(ans,1ll*g[s][t]*f[alln-s][x]%p
							*noe[s][allm-t]%p*noe[alln-s][lst-x]%p
							*(popc(s)-popc(t))%p);
					if(x==0) break;
				}
			}
	cout<<(n-ans+p)%p<<'\n';
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int T;
	cin>>T;
	while(T-->0) slove();
	return 0;
}