← 返回题目列表

Codeforces · 1210/F1

F1. 马立克和匹配(简单版)

中文机器翻译题面 查看原题

这是问题的一个更简单的版本。在此版本中,$$$n \le 6$$$。

Marek 正在努力为他的新算法问题创建强大的测试用例。你想知道它是什么吗?不,我们不会告诉你。但是,我们可以告诉您他如何生成测试用例。

Marek 选择整数 $$$n$$$ 和 $$$n^2$$$ 整数 $$$p_{ij}$$$ ($$$1 \le i \le n$$$, $$$1 \le j \le n$$$)。然后,他生成一个具有 $$$2n$$$ 个顶点的随机二分图。左侧有 $$$n$$$ 个顶点:$$$\ell_1、\ell_2、\dots、\ell_n$$$,右侧有 $$$n$$$ 个顶点:$$$r_1、r_2、\dots、r_n$$$。对于每个 $$$i$$$ 和 $$$j$$$,他以 $$$p_{ij}$$$ 的概率在顶点 $$$\ell_i$$$ 和 $$$r_j$$$ 之间放置一条边。

事实证明,只有在生成的图中存在完美匹配时,测试才会很强。这种情况发生的概率是多少?

可以证明,该值可以表示为 $$$\frac{P}{Q}$$$,其中 $$$P$$$ 和 $$$Q$$$ 是互质整数,$$$Q \not\equiv 0 \pmod{10^9+7}$$$。设 $$$Q^{-1}$$$ 为整数,其中 $$$Q \cdot Q^{-1} \equiv 1 \pmod{10^9+7}$$$。打印 $$$P \cdot Q^{-1}$$$ 模 $$$10^9+7$$$ 的值。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$\mathbf{1 \le n \le 6}$$$)。以下 $$$n$$$ 行描述了图中出现的每条边的概率。第 $$$i$$$ 行包含 $$$n$$$ 整数 $$$p_{i1}, p_{i2}, \dots, p_{in}$$$ ($$$0 \le p_{ij} \le 100$$$); $$$p_{ij}$$$ 表示 $$$\ell_i$$$ 和 $$$r_j$$$ 之间出现边缘的概率(以百分比表示)。

输出

打印一个整数 - 二部图中存在完美匹配的概率,对于上面定义的 $$$P$$$、$$$Q$$$ 可以写为 $$$P \cdot Q^{-1} \pmod{10^9+7}$$$ 。

示例

输入 #1

2
50 50
50 50

输出 #1

937500007

输入 #2

3
3 1 4
1 5 9
2 6 5

输出 #2

351284554

注意

在第一个样本测试中,下面的 $$$16$$$ 图表中的每一个都是等概率的。其中,$$$7$$$ 具有完美匹配:

因此,概率等于 $$$\frac{7}{16}$$$。由于 $$$16 \cdot 562\,500\,004 = 1 \pmod{10^9+7}$$$,测试用例的答案是 $$$7 \cdot 562\,500\,004 \mod{(10^9+7)} = 937\,500\,007$$$。