某人在玩一个非常神奇的游戏。这个游戏中有一个左右各 $n$ 个点的二分图，图中的边会按照一定的规律随机出现。
为了描述这些规律，某人将这些边分到若干个组中。每条边或者不属于任何组 (这样的边一定不会出现)，或者只属于一个组。
有且仅有以下三类边的分组：
这类组每组只有一条边，该条边恰好有 $50 \%$ 的概率出现。
这类组每组恰好有两条边，这两条边有 $50 \%$ 的概率同时出现，有 $50 \%$ 的概率同时不出现。
这类组每组恰好有两条边，这两条边恰好出现一条，各有 $50\%$ 的概率出现。
组和组之间边的出现都是完全独立的。
某人现在知道了边的分组和组的种类，想要知道完美匹配数量的期望是多少。你能帮助她解决这个问题吗？
如果你对完美匹配和期望的定义很熟悉，那么你可以跳过本段。
对于一个左右各 $n$ 个点的二分图，它的一个完美匹配是指 $n$ 条没有公共点的边构成的匹配。
两个完美匹配不同，当且仅当它们至少含有一条不同的边。一个二分图完美匹配的数量定义为这张图能找到的两两不同的完美匹配的数量。
在题目的图中，边都是随机出现的，因此这个图中完美匹配的数量是一个随机变量。一个 (离散型) 随机变量 $X$ 的期望定义为以概率为权，$X$ 所有可能取值的加权平均数，即
$$ \sum_{x \in V(X)} P(X = x) \cdot x $$
其中 $V(X)$ 表示 $X$ 所有可能的取值集合，$P(X = x)$ 表示 $X$ 取值为 $x$ 的概率。
第一行两个数 $n, m$ ($n \leq 15, m \leq n^2$)，表示图左右点数的数量和边的组的个数。
我们用 $(a, b)$ ($1 \leq a, b \leq n$) 表示一条左端点为二分图左侧第 $a$ 个点，右端点为二分图右侧第 $b$ 个点的边。
接下来 $m$ 行，每行描述一个组。开头第一个数 $t$ 表示组的种类，$t = 0$ 表示是一条边的组，$t = 1$ 表示是两条边的组中的第一种，$t = 2$ 表示是两条边的组中的第二种。
如果 $t = 0$，接下来两个数 $a_1, b_1$ 表示组内的第一条边；否则，接下来四个数 $a_1, b_1, a_2, b_2$，表示该组内的两条边分别为 $(a_1, b_1)$ 和 $(a_2, b_2)$。保证每条边至多出现一次。
假设期望的完美匹配数量是 $E$。输出一行表示 $$ (2^n E) \bmod (10^9 + 7) $$
可以看出上式一定是一个整数。
先考虑 $t = 0$ 的情况。容易发现，可以使用状态压缩 DP 来完成。
记 $f_{S, T}$ ($S, T$ 是 $\{1, 2, \cdots, n\}$ 的子集，且 $|S| = |T|$) 表示二分图左侧取集合 $S$ 中的点，右侧取集合 $T$ 中的点，所得的完美匹配数量的期望。那么有边界 $f_{\varnothing, \varnothing} = 1$ (注意空匹配也是完美匹配哦)。
对于 $f_{S, T}$。我们考虑其中任意一个点，比如说着左侧编号最小的点 $i$ ($i = \min S$)，考虑它和右侧哪条边相连。枚举边 $(i, j)$，其中 $j \in T$，由于这条边有 $p = \dfrac 12$ 的概率出现，因此如果这条边出现，那么它对应的完美匹配数量应该是 $p \cdot f_{S \setminus \{i\}, T \setminus \{j\}}$。将所有的 $j$ 相加，即得转移方程
$$ f_{S, T} = \sum_{\quad\ \ j \in T \\ (i, j) \textrm{is an edge}} p \cdot f_{S \setminus \{i\}, T \setminus \{j\}} $$
由于前置状态的 $|S|, |T|$ 较小，因此可以根据集合大小枚举。不过由于状态数是 $\sum\limits_{i=0}^n \dbinom ni^2 = \dbinom {2n} n \approx 1.6 \times 10^8$，状态较多。因此使用记忆化搜索，用 map 或 Hash 存储。
接下来考虑 $t \neq 0$ 的情况。
$t \neq 0$ 意味着就有两条 (相互之间有关系的) 边。我们尝试着将它们分离成两条独立的边加入，当然，这会对答案造成影响。
先考虑第一种情况：即对于边 $e_1, e_2$，要么同时出现，要么同时不出现 (这里假设 $e_1, e_2$ 自身不相交，否则忽略它)。那么如果将 $e_1, e_2$ 独立加入，则计算得到的含有 $e_1, e_2$ 的匹配 (即同时出现) 所对应的概率系数为 $\dfrac 14$。
然而实际上它们同时出现的概率为 $\dfrac 12$，即应该乘的概率系数应为 $\dfrac 12$。因此我们可以加一个双重边 (四点组)，即令 $e' = e_1 \cup e_2$，然后令它的出现概率为 $p' = \dfrac 14$。
这样一来，如果我们在 DP 时同时算上它，最终对应匹配乘上的概率系数就为 $\dfrac 14 +\dfrac 14 = \dfrac 12$。
如果这个匹配不同时含有 $e_1$ 和 $e_2$，那么最终算得的概率是不会产生任何影响的。
对第二种情况也是类似地：此时两条边恰好出现一条。那么含有 $e_1, e_2$ 的匹配就不可能出现了 (即概率系数应为 $0$)，而独立加入的概率依然是 $\dfrac 14$，因此只需加一个负权的双重边 (即概率 $p' = - \dfrac 14$)，把多算的抵消掉即可。
最终卡卡常，时间应该还是蛮松的。(下面这份代码是 C++11 的，因为我用了 STL 的 unordered_map <uint, ll>)
#include <bits/stdc++.h>
#define M 510
using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef pair <uint, ll> pul;
typedef unordered_map <uint, ll> mul;
const ll mod = 1000000007, inv2 = 500000004, inv4 = 250000002, _inv4 = 750000005;
struct edge{
uint v; ll p;
edge (uint value = 0, ll prob = 0): v(value), p(prob) {}
}e[M];
int n, m, E = 0;
int t, a, b;
uint id, id1;
ll ans;
mul f;
inline void add(ll &x, const ll y) {(x += y) >= mod ? x -= mod : 0;}
ll dp(uint state){
if(!state) return 1ll;
mul::iterator it = f.find(state);
if(it != f.end()) return it->second;
ll res = 0; uint id;// low = state & -state;
for(int i = 1; i <= E; ++i)
// id \subset state && highbit(state) \in id
// using highbit() will run faster than using lowbit() in constant factor.
if((id = e[i].v) == (id & state) && (id << 1 > state))
res = (res + dp(state ^ id) * e[i].p) % mod;
f.insert(pul(state, res));
return res;
}
int main(){
int i;
scanf("%d%d", &n, &m);
for(i = 0; i < m; ++i){
scanf("%d%d%d", &t, &a, &b);
id = 1u << a - 1 | 1u << n + b - 1;
e[++E] = edge(id, inv2);
if(!t) continue;
scanf("%d%d", &a, &b);
id1 = 1u << a - 1 | 1u << n + b - 1;
e[++E] = edge(id1, inv2);
if(id & id1) continue;
e[++E] = edge(id | id1, t == 1 ? inv4 : _inv4);
}
ans = dp((1u << (n << 1)) - 1) * (1 << n) % mod;
printf("%lld\n", ans);
return 0;
}
坑1：转移的时候，如果固定 $i$ 为某侧编号最大的点 (比如 $i = \max S$)，状态数可能会稍微减少一点 (即常数可能会稍微小一点，不过并不明显)。