考虑统计所有的方案，每种方案的能够出现的概率的和，再乘上要求的2^n就是答案。
f[s]表示s这个集合完美匹配完了之后，每种方案的出现概率的和
状态数看似是2^30的，
但是由于s的sz必须是偶数，所以大概是1e8
可以直接爆搜，6s
对于第二第三类边？
巧妙的做法是：
拆成独立50%的边，对于同时选择的时候，概率会和实际有不同，所以，，，
对于第二类，额外有25%的概率进行同时选择，对于第三类，额外有-25%的概率进行同时选择。（-25%理解为配上系数）
在两条边左部点编号较小的考虑这种情况即可。
每种方案概率必然算的是对的。
见代码：
注意，返回mp[s]，不是mp.count(s)
// luogu-judger-enable-o2 #include<bits/stdc++.h> #define reg register int #define il inline #define fi first #define se second #define mk(a,b) make_pair(a,b) #define numb (ch^'0') #define pb push_back #define solid const auto & #define enter cout<<endl #define pii pair<int,int> using namespace std; typedef long long ll; template<class T>il void rd(T &x){ char ch;x=0;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x);} template<class T>il void output(T x){if(x/10)output(x/10);putchar(x%10+'0');} template<class T>il void ot(T x){if(x<0) putchar('-'),x=-x;output(x);putchar(' ');} template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar(' ');} namespace Modulo{ const int mod=1e9+7; int ad(int x,int y){return (x+y)>=mod?x+y-mod:x+y;} void inc(int &x,int y){x=ad(x,y);} int mul(int x,int y){return (ll)x*y%mod;} void inc2(int &x,int y){x=mul(x,y);} int qm(int x,int y=mod-2){int ret=1;while(y){if(y&1) ret=mul(x,ret);x=mul(x,x);y>>=1;}return ret;} } using namespace Modulo; namespace Miracle{ const int N=16; int iv2,iv4; int n,m; struct node{ int c,d,v; node(){} node(int cc,int dd,int vv){ c=cc;d=dd;v=vv; } }ano[1600]; int to[N]; int hf; unordered_map<int,int>mp; int merge(int le,int ri){ return (le<<n)|ri; } int dp(int s){ // cout<<" ss "<<s<<endl; if(s==0) return 1; if(mp.count(s)) return mp[s]; int le=s>>n,ri=s&hf; int now=le&(-le),id=log2(now); int ret=0; // cout<<"af "<<s<<" le "<<le<<" ri "<<ri<<endl; // cout<<" now "<<now<<" id "<<id<<endl; for(reg t=0;t<n;++t){ // cout<<" tt "<<t<<endl; if(to[id]&(1<<t)){ if(ri&(1<<t)){ ret=ad(ret,mul(iv2,dp(merge(le-now,ri-(1<<t))))); int lp=id*100+t; // cout<<"lp "<<lp<<endl; if(ano[lp].v){ int c=ano[lp].c,d=ano[lp].d; // cout<<" c "<<c<<" d "<<d<<" id "<<id<<" t "<<t<<endl; if(((le-now)&(1<<c))&&(((ri-(1<<t))&(1<<d)))) ret=ad(ret,mul(ano[lp].v,dp(merge(le-now-(1<<c),ri-(1<<t)-(1<<d))))); } } } } return mp[s]=ret; } int main(){ iv2=qm(2); iv4=qm(4); rd(n);rd(m); int t,x,y,c,d; for(reg i=1;i<=m;++i){ rd(t);rd(x);rd(y); --x;--y; if(t==0){ to[x]|=(1<<y); }else if(t==1){ rd(c);rd(d); --c;--d; if(c==x) { to[x]|=(1<<d); to[x]|=(1<<y); } else{ if(c<x) swap(x,c),swap(y,d); to[x]|=(1<<y); to[c]|=(1<<d); ano[x*100+y]=node(c,d,iv4); } }else if(t==2){ rd(c);rd(d); --c;--d; if(c==x) { to[x]|=(1<<d); to[x]|=(1<<y); } else{ if(c<x) swap(x,c),swap(y,d); to[x]|=(1<<y); to[c]|=(1<<d); ano[x*100+y]=node(c,d,mod-iv4); } } } hf=(1<<n)-1; int ans=dp((1<<(2*n))-1); ans=mul(ans,qm(2,n)); ot(ans); return 0; } } signed main(){ Miracle::main(); return 0; } /* Author: *Miracle* */
这个边的拆分很妙啊，因为是计算概率，所以可以配合适的系数，
就划归成了第一类边