题解 P4547 【[THUWC2017]随机二分图】

· · 题解

根据题意，题目中所求的即为所有n!种完美匹配的各自的出现概率之和再乘上2^n的值。

发现n很小，考虑状压DP。设f_{S,T}为左部图匹配情况为S，右部图匹配情况为T的期望，可以得到转移为：

f_{S,T}=\sum_{x \subseteqq S \land y \subseteqq T }f_{S \oplus x,T \oplus y} \times p_e

其中x,y为边e的在两个部图的两个端点，p_e为这条边的出现概率，转移的含义为加上e这条边后x和y实现了匹配。

发现直接这样转移会算重，所以要事先固定一种转移顺序，可以是每次在S中去除最高位来转移，也就是从低位向高位转移，这样就保证不会算重了。

然后考虑如何解决每条边的出现概率，第一组边不用特殊考虑，概率为\frac{1}{2}。考虑是否可以把第二组和第三组边也转化为第一种的形式。可以先将第二组和第三组边的两条边都以概率为\frac{1}{2}加入，对于第二组边，这时两条边同时出现的概率为\frac{1}{4}，不符合题目\frac{1}{2}的要求，因此再加入同时选这两条边的情况，概率为\frac{1}{4}，对于第三组边，再加入同时选这两条边的情况，概率为-\frac{1}{4}。根据期望的线性性，发现这样处理是正确的，并且恰好符合了题目的要求。

第二组和第三组边中，若两条边有交集，即两条边为一个点连向另外两个点，此时是不用加上同时选这两条边的情况的，因为题目所求为完美匹配，一个点匹配两个点的情况是不存在的。

处理完边后，记忆化搜索来实现状压DP即可。

code: 
#include<bits/stdc++.h>
#define maxs 70010
#define p 1000000007
#define inv2 500000004
#define inv4 250000002
#define sta(x) (1<<(x-1))
using namespace std;
typedef long long ll;
template<typename T> inline void read(T &x)
{
    x=0;char c=getchar();bool flag=false;
    while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    if(flag)x=-x;
}
int n,m,cnt;
map<int,ll> f[maxs];
struct node
{
    ll s,t,v;
}e[maxs];
ll dp(int S,int T)
{
    if(!S) return 1;
    if(f[S].count(T)) return f[S][T];
    for(int i=1;i<=cnt;++i)
    {
        ll s=e[i].s,t=e[i].t,v=e[i].v;
        if((S|s)!=S||(T|t)!=T||S>=(s<<1)) continue;
        f[S][T]=(f[S][T]+dp(S^s,T^t)*v%p)%p;
    }
    return f[S][T];
}
int main()
{
    read(n),read(m);
    for(int i=1;i<=m;++i)
    {
        int opt,x,y;
        read(opt),read(x),read(y),e[++cnt]=(node){sta(x),sta(y),inv2};
        if(opt)
        {
            read(x),read(y);
            if(!((sta(x)&e[cnt].s)||(sta(y)&e[cnt].t)))
            {
                cnt++;
                if(opt==1) e[cnt]=(node){sta(x)|e[cnt-1].s,sta(y)|e[cnt-1].t,inv4};
                else e[cnt]=(node){sta(x)|e[cnt-1].s,sta(y)|e[cnt-1].t,p-inv4};
            }
            e[++cnt]=(node){sta(x),sta(y),inv2};
        }
    }
    printf("%lld",dp((1<<n)-1,(1<<n)-1)*(1<<n)%p);
    return 0;
}