洛谷P4547 [THUWC2017]随机二分图题解

题目链接：P4547 [THUWC2017]随机二分图

题意：

某人在玩一个非常神奇的游戏。这个游戏中有一个左右各 \(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\)，表示图左右点数的数量和边的组的个数。我们用 \((a,b)\) （其中 \(1 \le a,b \le 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) \] 可以看出上式一定是一个整数。

数据范围：

对于 \(100\%\) 的数据，\(n \le 15\)。

期望+状压dp神仙题

~~我居然在独立性的问题上瞎折腾了半天（多亏了Roundgod，不然我估计还在折腾）~~

先看 \(t=0\) 的情况。因为 \(n \le 15\) ，所以考虑状压。

设 \(f_{S,T}\) 表示在二分图中取「左侧点集的子集 \(S\) 」和「右侧点集的子集 \(T\) 」，且 \(|S|=|T|\) 时所得的完美匹配数量的期望。

显然有边界 \(f_{\varnothing,\varnothing} = 1\) 。（空匹配也是完美匹配）

考虑从每一条边拼接转移 \[ f_{S,T} = \sum _ {i \in S \land j \in T \land (i,j) \in R} p_e \times f_{S \setminus \{i\}, T\setminus \{j\}} \] 但是这样转移会重复计算，因此要固定一种转移顺序

这里可以强制用状态最低位来转移（实际上最高位的转移在常数上会更快）

更详细地，这里的重复计算在于：

对于某种完全相同的匹配，我们按不同的加边顺序算了多次

显然这会导致答案错误，因此我们要固定一种加边顺序。

例如我们在 \((S,T)\) 把 \(a,b\) 去了，然后在 \(\left(S \setminus \{a\}, T\setminus \{b\}\right)\) 去掉了 \(c,d\)

结果接下来我们又枚举了 \((S,T)\) 去 \(c,d\) ，在 \(\left(S \setminus \{c\}, T\setminus \{d\}\right)\) 去 \(a,b\) 。

此时的状态数为 \[ \sum\limits_{i=0}^n \dbinom{n}{i}^2 = \dbinom{2n}{n} \] \(n=15\) 时状态数约为 \(1.6\times 10^8\) 。

因为实际上不会用到这么多空间，考虑使用unordered_map存储。

接下来考虑 \(t\ne 0\) 的情况

下面假设 \(e_1,e_2\) 不相交，否则我们跳过它（因为题目要求的是完美匹配，所以不存在一个点匹配两个点的情况）

第一种情况，两条边有 \(50\%\) 的概率同时出现，有 \(50\%\) 的概率同时不出现。

考虑把它们拆成两条边独立计算贡献

然后我们会发现 \(e_1,e_2\) 同时出现的概率居然只剩下了 \(\dfrac{1}{4}\) （所幸其他倒是没影响）

于是根据期望的线性性质（ \(E(A+B) = E(A) + E(B)\) ，即和的期望等于期望的和），我们可以增加一个出现期望为 \(\dfrac{1}{4}\) 的 \((e_1,e_2)\) ， \((e_1,e_2)\) 表示两条边同时选

这样 \(\dfrac{1}{4} + \dfrac{1}{4} = \dfrac{1}{2}\) ，就没有问题啦！

同理，第二种情况，两条边恰好出现一条，各有 \(50\%\) 的概率出现。

还是拆成两条边独立计算贡献，然后会发现他们是不可能同时出现的

所以要去掉那个 \(\dfrac{1}{4}\) 。类似地，我们增加一个期望为 \(-\dfrac{1}{4}\) 的 \((e_1,e_2)\) 。

时间复杂度 \(o(2^{2n}n^2)\) ，注意是小o记号（非紧上界记号）

真实的复杂度可能很复杂，反正能过就行（（

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
#include <unordered_map>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
// #define N ((int)())
#define M ((int)(555))
const int mod = 1e9+7, inv2 = 500000004, inv4 = 250000002, _inv4 = 750000005;
int n,m,pos;
struct Edge {int v,p;} e[M];
unordered_map<int,int> f;
void add(int &x,int y) { (x+=y) >= mod ? x-=mod : 0;}
int dp(int st)
{
    if(!st) return 1;
    auto it = f.find(st);
    if(it != f.end()) return it->second;
    int res=0, id;
    for(int i=1; i<=pos; i++)
    {
        id=e[i].v;
        // 因为这里学习yhx巨佬的写法，下面是原注释。
        // id \subset state && highbit(state) \in id
		// using highbit() will run faster than using lowbit() in constant factor.
        // 这里要求了优先去除最高位来转移
        if(id == (id & st) && ((id << 1) > st))
            add(res, dp(st ^ id) * e[i].p % mod);
    }
    f.insert({st,res});
    return res;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i=1,t,a,b,st,_st; i<=m; i++)
    {
        cin >> t >> a >> b;
        st = (1 << (a-1)) | (1 << (n+b-1));
        e[++pos] = {st, inv2};
        if(!t) continue;
        cin >> a >> b;
        _st = (1 << (a-1)) | (1 << (n+b-1));
        e[++pos] = {_st, inv2};
        if(st & _st) continue;
        e[++pos] = {st | _st, t==1 ? inv4 : _inv4};
    }
    int res = dp(((1 << (n<<1)) - 1)) * (1 << n) % mod;
    cout << res << '\n';
    return 0;
}