CF1466H Finding satisfactory solutions

在本次比赛中走到这一步并非易事。通过解决之前的所有问题，你已经让众神印象深刻。因此，他们决定不再赐予你故事情节，而是直接给出正式题目描述。 考虑 $n$ 个代理人。每个代理人最初恰好拥有一个物品，第 $i$ 个代理人拥有编号为 $i$ 的物品。我们关注这些物品在代理人之间的重新分配。一次分配是合法的，当且仅当每个物品被分配给恰好一个代理人，并且每个代理人恰好被分配到一个物品。 每个代理人对物品有自己的偏好，可以用一个排列 $p$ 来描述，从最喜欢到最不喜欢依次排列。换句话说，如果 $i$ 在排列 $p$ 中出现在 $j$ 之前，则该代理人更喜欢物品 $i$ 而不是物品 $j$。一个偏好配置是一个长度为 $n$ 的排列列表，每个排列描述第 $i$ 个代理人的偏好。 可能存在一些代理人对物品的分配不满意。不满意的代理人可以选择不与其他代理人合作。在这种情况下，他们只会在自己最初拥有的物品之间进行交换（第 $i$ 个物品属于第 $i$ 个代理人）。这个小组内的代理人不关心组外代理人的满意度。然而，他们需要以一种方式交换物品，使得至少有一人变得更满意，并且没有人变得更不满意（与当前分配相比）。 形式化地，考虑一个合法的物品分配 $A$。令 $A(i)$ 表示分配给第 $i$ 个代理人的物品。再考虑一组代理人的子集，设 $S$ 为他们的编号集合。我们称这个代理人子集为不满意的，当且仅当存在一个合法分配 $B(i)$，满足： - 对于每个 $i \in S$，$B(i) \in S$。 - 没有 $i \in S$ 更喜欢 $A(i)$ 而不是 $B(i)$（即 $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$ 取模。

第一个测试样例中的分配仅对如下偏好配置是最优的： $2, 1$ $1, 2$ 如果某个代理人最想要自己最初拥有的物品，但实际分配给了他其他物品，他就会组成一个不满意的集合。因此，该分配对于其他任何偏好配置都不是最优的。 由 ChatGPT 4.1 翻译