LOJ2290 [THUWC2017]随机二分图

题意

某人在玩一个非常神奇的游戏。这个游戏中有一个左右各$n$个点的二分图,图中的边会按照一定的规律随机出现。
为了描述这些规律,某人将这些边分到若干个组中。每条边或者不属于任何组 (这样的边一定不会出现),或者只属于一个组。
有且仅有以下三类边的分组:

  • 这类组每组只有一条边,该条边恰好有$50\%$的概率出现。
  • 这类组每组恰好有两条边,这两条边有$50\%$的概率同时出现,有$ 50\%$的概率同时不出现。
  • 这类组每组恰好有两条边,这两条边恰好出现一条,各有$50\%$的概率出现。

组和组之间边的出现都是完全独立的。
某人现在知道了边的分组和组的种类,想要知道完美匹配数量的期望是多少。你能帮助她解决这个问题吗?
$n \leqslant 15$。

题解

这题本来是在THUWC2018之前写的,作为练习。但是题解到现在才写……
这道题算是一道比较神的题吧……$15$的范围容易想到状压。第一种边还是比较好处理的,但是对于第二种和第三种似乎非常棘手。于是我们考虑对第二种和第三种边进行拆边。具体拆边是这样的:
对于第二种边,我们把它拆分成两条单独的$50\%$的边,和$25\%$的两条边同时出现的边组。
对于第三种边,我们把它拆分成两条单独的$50\%$的边,和$-25\%$的两条边同时出现的边组。
这个拆分的过程,个人认为很难理解= =。我是从对答案的贡献的角度去理解的。比如说对于第二种边中出现的边组$(x_1,y_1,x_2,y_2)$,在$x_1$或$y_1$已经被匹配的时候能对匹配$(x_2,y_2)$产生$50\%$的贡献,在$x_2$或$y_2$已经被匹配的时候能对匹配$(x_1,y_1)$产生$50\%$的贡献,但是对同时匹配$(x_1,y_1),(x_2,y_2)$只能产生$25\%$的贡献,所以要补上$25\%$的同时出现的贡献。对于第三种情况,两条边同时存在的贡献多了$25\%$,所以要加一条贡献为$-25\%$的边。
然后就可以状压DP了。具体来说,设$dp[i][j]$表示二分图左侧匹配情况为$i$,右侧匹配情况为$j$的期望值。看上去过不了,但是有用的状态很少,其实是可过的。$dp$数组要用map存下来。转移并不复杂,在此不再赘述。
时间复杂度$O($能过??$)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<map>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF=1e9;
const int mod=1e9+7;
const int maxn=15;
const int maxm=250;
const long double eps=1e-9;
int to[maxm],nex[maxm],beg[maxm],extra[maxn][maxn];
int e;
struct node{
int x,y,val;
}edge[maxm];
map<ll,ll> dp[(1<<maxn)+10];
map<ll,ll>::iterator it;
inline int read(){
int x=0,flag=1;
char ch=getchar();
while(!isdigit(ch) && ch!='-')ch=getchar();
if(ch=='-')flag=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*flag;
}
inline int fpm(int a,int b){
int ans=1;
while(b){
if(b & 1)ans=1ll*ans*a%mod;
a=1ll*a*a%mod;
b/=2;
}
return ans;
}
inline void add(int x,int y){
to[++e]=y;
nex[e]=beg[x];
beg[x]=e;
}
int main(){
int i,j,k,m,n;
#ifndef ONLINE_JUDGE
freopen("LOJ2290.in","r",stdin);
freopen("LOJ2290.out","w",stdout);
#endif
n=read();m=read();
int cnt=0;
for(i=1;i<=m;i++){
int type=read();
if(type==0){
int x=read(),y=read();
add(x,y);
}
else{
int x=read(),y=read();edge[++cnt].x=read();edge[cnt].y=read();
add(x,y);add(edge[cnt].x,edge[cnt].y);
if(edge[cnt].x<x)swap(x,edge[cnt].x),swap(y,edge[cnt].y);
if(edge[cnt].x==x || edge[cnt].y==y)continue;
edge[cnt].val=type==1 ? 1 : -1;extra[x][y]=cnt;
}
}
dp[0][0]=1;
int Inv1=fpm(2,mod-2),Inv2=1ll*Inv1*Inv1%mod;
for(i=0;i<(1<<n);i++)
for(j=1;j<=n;j++){
if(i & (1<<(j-1)))continue;
for(it=dp[i].begin();it!=dp[i].end();it++){
int Set=it->first,Val=it->second;
for(k=beg[j];k;k=nex[k]){
if((1<<(to[k]-1)) & Set)continue;
(dp[i|(1<<(j-1))][Set|(1<<(to[k]-1))]+=1ll*Val*Inv1%mod)%=mod;
if(!extra[j][to[k]])continue;
int x=edge[extra[j][to[k]]].x,y=edge[extra[j][to[k]]].y;
if((i & (1<<(x-1))) || (Set & (1<<(y-1))))continue;
(dp[i|(1<<(j-1))|(1<<(x-1))][Set|(1<<(to[k]-1))|(1<<(y-1))]+=
1ll*Val*Inv2*edge[extra[j][to[k]]].val%mod+mod)%=mod;
}
}
break;
}
int ans=dp[(1<<n)-1][(1<<n)-1];
for(i=1;i<=n;i++)ans=1ll*ans*2%mod;
printf("%d\n",ans);
return 0;
}