看了一眼觉得是求出图对图统计完美匹配的个数（可能之前做过这样模拟题弃疗了，一直心怀恐惧。。。
然后说是统计一下每种匹配出现的概率，也就是，当前左边点匹配状态为S，右边点匹配状态为T，每种匹配出现的概率的总和作为\(f[S][T]\)，我们需要的就是\(f[2^{n} - 1][2^{n} - 1]\)
然而，会发现转移起来似乎非常麻烦,例如，假如两条边一起出现，各自匹配出现的概率是多少？
我们把每组边拆开，变成每条边在匹配中有50%概率出现，一组边同时在匹配中出现的概率是25%，如果t = 2,那么概率就是-25%
为什么呢，对于t = 1的边，两条肯定一起出现，那么如果我们算第一条边进入匹配，概率是50%，算第二条边进入匹配，概率也是50%，但是由于两条边一起出现的特殊性质，我们按照这个方法算，如果两个匹配都出现的概率是25%，但是两条匹配都出现的概率是50%，我们就加上一个25%两条边一起匹配
同理，对于t = 2的边，第一条边进去匹配是50%，第二条边进入匹配是50%，然而两条边一起进入匹配是不可能的，只有减掉那25%的概率了
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <map>
//#define ivorysi
#define pb push_back
#define space putchar(‘ ‘)
#define enter putchar(‘\n‘)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define mo 974711
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < ‘0‘ || c > ‘9‘) {
if(c == ‘-‘) f = -1;
c = getchar();
}
while(c >= ‘0‘ && c <= ‘9‘) {
res = res * 10 + c - ‘0‘;
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {putchar(‘-‘);x = -x;}
if(x >= 10) {
out(x / 10);
}
putchar(‘0‘ + x % 10);
}
const int MOD = 1000000007;
int N,M,tot,fir[(1 << 15) + 1];
struct Edge{
int a[2],b[2],val;
}E[10005];
vector<int> MK[20];
map<int,int> f[(1 << 15) + 5];
int fpow(int x,int c) {
int res = 1,t = x;
while(c) {
if(c & 1) res = 1LL * res * t % MOD;
t = 1LL * t * t % MOD;
c >>= 1;
}
return res;
}
void Init() {
read(N);read(M);
int t,a0,a1,b0,b1;
int Inv2 = (MOD + 1) / 2,Inv4 = 1LL * Inv2 * Inv2 % MOD;
for(int i = 1 ; i <= M ; ++i) {
read(t);read(a0);read(b0);
if(t == 0) {
E[++tot].a[0] = a0;E[tot].b[0] = b0;E[tot].val = Inv2;
MK[a0].pb(tot);
}
else {
read(a1);read(b1);
E[++tot].a[0] = a0;E[tot].b[0] = b0;E[tot].val = Inv2;MK[a0].pb(tot);
E[++tot].a[0] = a1;E[tot].b[0] = b1;E[tot].val = Inv2;MK[a1].pb(tot);
E[++tot].a[0] = a0;E[tot].b[0] = b0;E[tot].a[1] = a1;E[tot].b[1] = b1;E[tot].val = Inv4;
MK[a0].pb(tot);MK[a1].pb(tot);
if(t == 2) E[tot].val = MOD - Inv4;
}
}
}
void update(int &x,int y) {
x += y;
while(x >= MOD) x -= MOD;
}
void Solve() {
fir[0] = 1;
for(int i = 1 ; i < (1 << N) ; ++i) {
fir[i] = min(fir[i >> 1] + 1,(i & 1) ? N + 1 : 1);
}
f[0][0] = 1;
for(int S = 0 ; S < (1 << N) ; ++S) {
for(auto k : f[S]) {
int T = k.fi,val = k.se;
//printf("%d %d %d\n",S,T,val);
for(auto id : MK[fir[S]]) {
if(T >> (E[id].b[0] - 1) & 1) continue;
if(S >> (E[id].a[0] - 1) & 1) continue;
if(E[id].a[1]) {
if(E[id].a[0] == E[id].a[1] || E[id].b[0] == E[id].b[1]) continue;
if(T >> (E[id].b[1] - 1) & 1) continue;
if(S >> (E[id].a[1] - 1) & 1) continue;
int a0 = E[id].a[0] - 1,a1 = E[id].a[1] - 1;
int b0 = E[id].b[0] - 1,b1 = E[id].b[1] - 1;
update(f[S | (1 << a0) | (1 << a1)][T | (1 << b0) | (1 << b1)],1LL * val * E[id].val % MOD);
}
else {
int a0 = E[id].a[0] - 1,b0 = E[id].b[0] - 1;
update(f[S | (1 << a0)][T | (1 << b0)],1LL * val * E[id].val % MOD);
}
}
}
}
int ans = 1LL * fpow(2,N) * f[(1 << N) - 1][(1 << N) - 1] % MOD;
out(ans);enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Init();
Solve();
return 0;
}原文：https://www.cnblogs.com/ivorysi/p/9086285.html