分数: 1100 点
问题陈述
老师有一个隐藏的排列 P=(P_1,P_2,\ldots,P_N) of (1,2,\cdots,N)。 你将确定它。
为此,您准备了一系列整数对 (A_1,B_1),(A_2,B_2),\ldots,(A_{N(N-1)/2},B_{N(N-1)/2});这是所有形式对的排列 (a,b) (1 \le a < b \le N)。 现在,您将从头开始检查这些对。一对 (A_i, B_i),你会问是否 P_{A_i}<P_{B_i},老师会告诉你答案。 但是,如果您已经可以从之前的答案中确定该问题的答案,则您将跳过此问题。
求排列数 P,对于你的算法,你将不得不询问所有 \frac{N(N-1)}{2} 问题,模数 10^9+7.
约束
- 2 \le N \leq 400
- 1 \le A_i < B_i \le N
- (A_i,B_i) \neq (A_j,B_j) (i \neq j)
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N
A_1 B_1
A_2 B_2
\vdots
A_{N(N-1)/2} B_{N(N-1)/2}
输出
打印答案。
示例输入 1
2 1 2
示例输出 1
2
显然,对于任何排列 P,你需要问 1 问题。
示例输入 2
4 1 2 1 3 2 3 2 4 3 4 1 4
示例输出 2
4
考虑 以 P=(2,3,1,4) 为例。 在这种情况下,您将跳过第三个问题,因为您知道 P_1 < P_2 和 P_1 > P_3 根据之前的问题,您可以确定 P_2 > P_3。 因此, P=(2,3,1,4) 不应计算在内。
示例输入 3
5 1 2 2 3 3 4 4 5 1 5 1 3 2 4 3 5 1 4 2 5
示例输出 3
0