题目大意
给一张二分图，有左部点和右部点。
有三种边，第一种是直接从左部点连向右部点，出现概率为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; }