← 返回题目列表

Codeforces · 1466/H

H. 寻找满意的解决方案

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

在这场比赛中取得如此成绩并非易事。通过解决之前的所有问题,你给众神留下了深刻的印象。因此,他们决定不告诉你这个问题的故事,而是给予正式的声明。

考虑 $$$n$$$ 代理。他们每个人最初都只有一件物品,第 $$$i$$$ 个代理的物品编号为 $$$i$$$。我们有兴趣在代理之间重新分配这些项目。当且仅当每个项目都分配给一个代理,并且每个代理都分配了一个项目时,分配才有效。

每个代理对项目都有偏好,这可以通过从最理想到最不理想的项目排列 $$$p$$$ 来描述。换句话说,当$$$i$$$出现在排列$$$p$$$中之前时,代理更喜欢项目$$$i$$$而不是项目$$$j$$$。偏好配置文件是每个长度为 $$$n$$$ 的 $$$n$$$ 排列的列表,使得第 $$$i$$$ 排列描述第 $$$i$$$ 代理的偏好。

某些特工可能对物品分配不满意。一组不满意的代理可能会选择不与其他代理合作。在这种情况下,他们只会在他们之间交换他们最初拥有的物品(第$$$i$$$个物品属于第$$$i$$$个代理人)。该群体的代理人并不关心该群体之外的代理人的满意度。然而,他们需要以这样一种方式交换他们的物品:至少让其中一个人更快乐,并且没有一个人不快乐(与给定的任务相比)。

正式地,考虑有效的项目分配 — $$$A$$$。让 $$$A(i)$$$ 表示分配给第 $$$i$$$ 个代理的项目。另外,请考虑代理的子集。令 $$$S$$$ 为其索引的集合。当且仅当存在有效分配 $$$B(i)$$$ 且满足以下条件时,我们会说该代理子集不满意:

- 对于每个 $$$i \in S$$$,$$$B(i) \in S$$$。
- S$$$ 中没有代理人 $$$i \in S$$$ 更喜欢 $$$A(i)$$$ 而不是 $$$B(i)$$$($$$S$$$ 中没有代理人不那么高兴)。
- S$$$ 中至少一名代理人 $$$i \in S$$$ 更喜欢 $$$B(i)$$$ 而不是 $$$A(i)$$$($$$S$$$ 中的至少一名代理人更满意)。

如果没有代理子集不满意,则分配是最佳的。请注意,空子集不能不满足。可以证明,对于每个偏好配置文件,都存在一个最佳分配。

示例:考虑具有以下偏好配置文件的 $$$3$$$ 代理:

1. $$$[2, 1, 3]$$$
2. $$$[1, 2, 3]$$$
3. $$$[1, 3, 2]$$$

这样的作业:

- 第一个特工获得物品 $$$2$$$
- 第二个特工获得物品 $$$3$$$。
- 第三位特工获得物品 $$$1$$$。

看到代理集 $$$\{1, 2\}$$$ 不满意,因为他们可以通过以下方式重新分配其(初始)项目:

- 第一个特工获得物品 $$$2$$$。
- 第二个特工获得物品 $$$1$$$。
- 第三位特工获得物品 $$$3$$$。

这种重新分配将使第二个代理更快乐,并且对第一个代理没有影响。结果,第三个特工得到了一个对他来说更糟糕的物品,但这并不能阻止集合 $$$\{1,2\}$$$ 不满意(他不在这个集合中)。

以下分配是最佳的:

- 第一个特工获得物品 $$$2$$$。
- 第二个特工获得物品 $$$1$$$。
- 第三位特工获得物品 $$$3$$$。

给定分配 $$$A$$$,计算分配 $$$A$$$ 最佳的不同偏好配置文件的数量。由于答案可能很大,因此输出它对 $$$10^9+7$$$ 取模。

两个偏好配置文件是不同的,前提是它们为任何代理分配了不同的偏好排列。

输入

在输入的第一行中有一个整数 $$$n$$$ ($$$1 \leq n \leq 40$$$)。下一行包含 $$$n$$$ 空格分隔的整数,即从 $$$1$$$ 到 $$$n$$$ 的数字排列。第 $$$i$$$ 数字表示在最佳分配中分配给代理 $$$i$$$ 的项目。

输出

在单行中输出一个非负整数,即输入中给定的项目分配以 $$$10^9+7$$$ 为模的最佳偏好配置文件的数量。

示例

输入 #1

2
2 1

输出 #1

1

输入 #2

3
1 2 3

输出 #2

98

输入 #3

4
2 1 3 4

输出 #3

27408

注意

第一个测试用例的分配仅对于以下首选项配置文件是最佳的:

$$$2, 1$$$

$$$1, 2$$$

如果任何代理最想要他的初始项目并获得另一个项目,他将形成一个不满意的集合。因此,对于任何其他偏好配置文件来说,分配都不是最佳的。