P4547 [THUWC 2017] 随机二分图

# 滥用本题评测将被封号

某人在玩一个非常神奇的游戏。这个游戏中有一个左右各 $n$ 个点的二分图，图中的边会按照一定的规律随机出现。 为了描述这些规律，某人将这些边分到若干个组中。每条边或者不属于任何组 （这样的边一定不会出现），或者只属于一个组。 有且仅有以下三类边的分组： 0. 这类组每组只有一条边，该条边恰好有 $50\%$ 的概率出现。 1. 这类组每组恰好有两条边，这两条边有 $50\%$ 的概率同时出现，有 $50\%$ 的概率同时不出现。 2. 这类组每组恰好有两条边，这两条边恰好出现一条，各有 $50\%$ 的概率出现。 组和组之间边的出现都是完全独立的。 某人现在知道了边的分组和组的种类，想要知道完美匹配数量的期望是多少。你能帮助她解决这个问题吗？

无

无

## 【定义解释】 如果你对完美匹配和期望的定义很熟悉，那么你可以跳过本段。 对于一个左右各 $n$ 个点的二分图，它的一个完美匹配是指 $n$ 条没有公共点的边构成的匹配。 两个完美匹配不同，当且仅当它们至少含有一条不同的边。一个二分图完美匹配的数量定义为这张图能找到的两两不同的完美匹配的数量。 在题目的图中，边都是随机出现的，因此这个图中完美匹配的数量是一个随机变量。一个（离散型）随机变量 $X$ 的期望定义为以概率为权，$X$ 所有可能取值的加权平均数，即 $$ \sum_{x \in V(X)}P[X=x]\cdot x $$ 其中 $V(X)$ 表示 $X$ 所有可能的取值集合，$P[X=x]$ 表示 $X$ 取值为 $x$ 的概率。 ## 【数据规模和约定】 对于 $5\%$ 的数据 $n \le 5$ 。 对于另 $5\%$ 的数据 $n \le 8$ 。 对于另 $10\%$ 的数据 $n \le 10$ 。 对于另 $15\%$ 的数据，只有$t = 0$ 的情况。 对于另 $5\%$ 的数据，只有$t = 0$ 的情况，且$m = n^2$，也就是该图为一个完全图。 对于另 $20\%$ 的数据，只有 $t =0$ 或者 $t=1$ 的情况。 对于另 $20\%$ 的数据，只有 $t =0$ 或者 $t=2$ 的情况。 对于 $100\%$ 的数据，$n \le 15$。