题目大意
给一张二分图，有左部点和右部点。
有三种边，第一种是直接从左部点连向右部点，出现概率为50%。
第二种边一组里有两条边，这两条边同时出现或者不出现，概率都是50%。
第三种边一组里有两条边，这两条边只能出现一条，概率都是50%。
求这张图完美匹配数的期望
题解
一条边能够带来贡献的条件不是它出现了，而是它出现在了匹配中。所以我们应当直接计算每条边出现在最大匹配中的概率。
第一种边不用研究。
第二种边每一条条边出现在最大匹配中的概率都是50%。
两条边出现在最大匹配中的概率也是50%。
如果我们直接连两条50%的边的话，两条边同时出现的概率就是25%。
所以我们补一条两组的边，概率为25%。
第三种边同理，两条边出现在最大匹配中的概率是0%。
所以我们补一组-25%的边就好了。
dp的话，拿map记搜一下就好了。
代码
#include<iostream> #include<cstdio> #include<map> #define N 16 using namespace std; typedef long long ll; const int mod=1e9+7; map<int,int>mp; map<int,int>::iterator it; int lo[1<<N],tot,head[N],n,m; inline int rd(){int x=0;char c=getchar();bool f=0;while(!isdigit(c)){if(c=='-')f=1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}return f?-x:x; } inline ll power(ll x,ll y){ll ans=1;while(y){if(y&1)ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans; } inline void MOD(ll &x){while(x>=mod)x-=mod;} struct edge{int n,to,l;}e[N*N*2]; inline void add(int u,int v){int loo=lo[u&(-u)];e[++tot].n=head[loo];e[tot].to=u;head[loo]=tot;e[tot].l=v; } int DP(int s){if(!s)return 1;it=mp.find(s);if(it!=mp.end())return it->second;int loo=lo[s&(-s)];ll ans=0;for(int i=head[loo];i;i=e[i].n){int v=e[i].to;if((v&s)!=v)continue;ans+=1ll*DP(s^v)*e[i].l%mod;MOD(ans);}return mp[s]=ans; } int main(){n=rd();m=rd();int u1,v1,u2,v2,ma=(1<<n)-1,opt;ll n2=power(2,mod-2),n4=power(4,mod-2);lo[1]=1;int cc=1;for(int i=2;i<=n;++i)cc<<=1,lo[cc]=i;for(int i=1;i<=m;++i){opt=rd();if(opt==0){u1=rd();v1=rd();u1--;v1--;int s1=(1<<u1)|(1<<v1+n); add(s1,n2);} else if(opt==1){u1=rd()-1;v1=rd()-1;u2=rd()-1;v2=rd()-1;int s1=(1<<u1)|(1<<v1+n),s2=(1<<u2)|(1<<v2+n);add(s1,n2);add(s2,n2); if(!(s1&s2)){add(s1|s2,n4);}}else{u1=rd()-1;v1=rd()-1;u2=rd()-1;v2=rd()-1;int s1=(1<<u1)|(1<<v1+n),s2=(1<<u2)|(1<<v2+n);add(s1,n2);add(s2,n2); if(!(s1&s2)){add(s1|s2,mod-n4);}}}cout<<1ll*DP(ma|(ma<<n))*power(2,n)%mod;return 0; }
