先看(O(n!))的怎么做？
枚举一个排列（完美匹配），计算这个匹配的边一定出现（其它边随意）的概率。
若组0、1、2有恰好一条边在这个匹配，则概率(*1/2)
若组1有恰好两条边，则概率(*1/2)
若组2有恰好两条边，则概率(*0)
考虑只有组0的情况，显然设(f[i][S])表示左边确立了前i个，右边选了S，的概率和，就好了。
加入组1，把它拆成两条 组0的边，发现会少计算1/4的两条边同时选，加上这个。
加入组2，把它拆成两条 组0的边，发现会多计算1/4的两个边同时选，减去这个。
然后设一个(f[S1][S2])表示左边选了S1,右边选了S2的概率和。
需要确立一个转移顺序，也就是每次转移必须使S1的最低的0变成1.
状态上限是(sum_{i=0}^{n}C(n,i)^2=C(2n,n)≈1.5*10^8)，加上转移复杂度(O(n))TLE了。
发现这个状态跑不满，用记忆化+hash表转移，状态数不太会证。
Code：
#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, _b = y; i <= _b; i ++)
#define ff(i, x, y) for(int i = x, _b = y; i < _b; i ++)
#define fd(i, x, y) for(int i = x, _b = y; i >= _b; i --)
#define ll long long
#define pp printf
#define hh pp("
")
using namespace std;
const int mo = 1e9 + 7;
ll ksm(ll x, ll y) {
ll s = 1;
for(; y; y /= 2, x = x * x % mo)
if(y & 1) s = s * x % mo;
return s;
}
const int N = 16;
ll ni2 = ksm(2, mo - 2), ni4 = ksm(4, mo - 2);
int n, m;
int b[N][N];
ll c[N][N][4], c0[N];
map<int, ll> f;
ll calc(int s1, int s2) {
if(s1 == s2 && s1 == (1 << n) - 1) return 1;
int s3 = s1 + (s2 << n);
if(f.count(s3)) return f[s3];
ll ans = 0;
ff(i, 0, n) if(!(s1 >> i & 1)) {
ff(j, 0, n) if(b[i][j] && !(s2 >> j & 1)) {
ans = (ans + calc(s1 | (1 << i), s2 | (1 << j)) * ni2) % mo;
}
fo(j, 1, c0[i]) {
if(!(s2 >> c[i][j][0] & 1) && !(s1 >> c[i][j][1] & 1) && !(s2 >> c[i][j][2] & 1))
ans = (ans + calc(s1 | (1 << i) | (1 << c[i][j][1]), s2 | (1 << c[i][j][0]) | (1 << c[i][j][2])) * c[i][j][3]) % mo;
}
break;
}
return f[s3] = ans;
}
int main() {
scanf("%d %d", &n, &m);
fo(i, 1, m) {
int t, a1, b1, a2, b2;
scanf("%d %d %d", &t, &a1, &b1);
a1 --; b1 --;
if(t == 0) {
b[a1][b1] = 1;
} else {
scanf("%d %d", &a2, &b2);
a2 --; b2 --;
if(a1 > a2) swap(a1, a2), swap(b1, b2);
b[a1][b1] = 1;
b[a2][b2] = 1;
if(a1 == a2 || b1 == b2) continue;
c0[a1] ++;
c[a1][c0[a1]][0] = b1;
c[a1][c0[a1]][1] = a2;
c[a1][c0[a1]][2] = b2;
c[a1][c0[a1]][3] = t == 1 ? ni4 : mo - ni4;
}
}
ll ans = calc(0, 0);
fo(i, 1, n) ans = ans * 2 % mo;
pp("%lld
", ans);
}