orz神仙题
考虑只有(t=0)的时候怎么做
其实等价于求完美匹配的个数，但是我们有一个更为一般的(dp)可以写，设(dp_{S,T})表示在一左部点里匹配的点集是(S)，右部点里匹配的点集是(T)的期望完美匹配个数
我们可以枚举一条边((i,j))，表示当前匹配的边是((i,j))，于是就有
[dp_{S,T}=sum_{i
otin S,j
otin T,(i,j)in E}dp_{S/i,T/j} imes p_{i,j}
]
(S/i)表示集合(S)去掉(i)后的到的集合
但是这样求出来的东西好像不是很对，因为对于某一种完全匹配，我们按照不同的加边顺序算了多次，于是我们钦定一个加边顺序，比如先加入编号小的点，这样就不会算重
由于(|S|=|T|)，所以这样的复杂度是(sum_{i=0}^ninom{n}{i}^2=inom{2n}{n})，还是比较科学的
再来考虑(t>0)的情况
对于(t=1)的边组((u,v,a,b))，我们还是先把((a,b),(u,v))都加入边集出现的概率视为(frac{1}{2})；对于一组完美匹配，如果((a,b),(u,v))其中之一出现在了里面，那么我们算进去的概率是(frac{1}{2})，这符合题意：但是当((a,b),(u,v))都出现了，我们算的概率是(frac{1}{2} imes frac{1}{2}=frac{1}{4})，但真实的出现概率却是(frac{1}{2})
所以只有在这两条边都出现的情况下我们才会错误计算，于是我们加一条四元边((u,v,a,b))，出现概率为(frac{1}{4})，这样对于一组((a,b),(u,v))都出现的完美匹配，我们计算的概率就是(frac{1}{4}+ frac{1}{4}=frac{1}{2})，这样算就正确了。
同理，对于(t=2)的情况，我们加一条四元边((u,v,a,b))出现的概率为(-frac{1}{4})即可
代码
#include <tr1/unordered_map>
#include <bits/stdc++.h>
#define re register
using namespace std::tr1;
const int mod = 1e9 + 7, inv2 = 500000004, inv4 = 250000002, _inv4 = 750000005;
unordered_map<int, int> dp, f;
inline int qm(int x) { return x >= mod ? x - mod : x; }
int se[5005], sp[5005], n, m, M;
int dfs(int s) {
if (!s)
return 1;
if (f[s])
return dp[s];
int res = 0;
f[s] = 1;
for (re int i = 1; i <= M; i++)
if ((se[i] & s) == se[i] && se[i] > s / 2)
res = qm(res + 1ll * sp[i] * dfs(se[i] ^ s) % mod);
// printf("%d %d
",s,res);
return dp[s] = res;
}
int main() {
scanf("%d%d", &n, &m);
for (re int t, u, v, a, b, i = 1; i <= m; i++) {
scanf("%d%d%d", &t, &u, &v);
se[++M] = (1 << (u - 1)) | (1 << (v + n - 1));
sp[M] = inv2;
if (!t)
continue;
scanf("%d%d", &a, &b);
se[++M] = (1 << (a - 1)) | (1 << (b + n - 1));
sp[M] = inv2;
if (se[M] & se[M - 1])
continue;//当(a,b),(u,v)有交点的时候，由于不可能同时存在于完美匹配里，所以没有必要加入四元边
se[M + 1] = se[M] | se[M - 1];
sp[++M] = (t == 1 ? inv4 : _inv4);
}
// for(re int i=1;i<=M;i++) printf("%d %d
",se[i],sp[i]);
printf("%d
", 1ll * (1 << n) * dfs((1 << (n + n)) - 1) % mod);
return 0;
}