Maximize Minimum Difference

题目描述

注意：本题时间限制为 4s，是默认时间限制的两倍。

哞！给定一个整数 $N$（$2\le N\le 2000$）。考虑所有对 $[0,1,2\dots, N-1]$ 的排列 $p=[p_0,p_1,\dots, p_{N-1}]$。令 $f(p)=\min_{i=0}^{N-2}|p_i-p_{i+1}|$ 表示 $p$ 中任意两个相邻元素之间的最小绝对差。并令 $S$ 表示所有使 $f(p)$ 取得最大可能值的排列 $p$ 的集合。

另外给定 $K$（$0\le K\le N$）个形如 $p_i=j$（$0\le i,j<N$）的约束。在满足所有约束的前提下，统计集合 $S$ 中排列的数量，并对 $10^9+7$ 取模。

输入格式

第一行包含 $T$（$1\le TN\le 2\cdot 10^4$）和 $N$，表示你需要解决 $T$ 个相互独立的测试用例，每个用例由一组不同的约束指定。

每个测试用例以 $K$ 开始，随后有 $K$ 行，每行包含 $i$ 和 $j$。保证： 同一个 $i$ 在同一测试用例中不会出现超过一次。 同一个 $j$ 在同一测试用例中不会出现超过一次。

输出格式

对每个测试用例，输出一行答案，对 $10^9+7$ 取模。

3 4
0
1
1 1
2
0 2
2 3

2
0
1

9 11
2
0 5
6 9
3
0 5
6 9
1 0
4
0 5
6 9
1 0
4 7
5
0 5
6 9
1 0
4 7
2 6
6
0 5
6 9
1 0
4 7
2 6
9 3
7
0 5
6 9
1 0
4 7
2 6
9 3
5 2
8
0 5
6 9
1 0
4 7
2 6
9 3
5 2
7 4
9
0 5
6 9
1 0
4 7
2 6
9 3
5 2
7 4
3 1
10
0 5
6 9
1 0
4 7
2 6
9 3
5 2
7 4
3 1
8 10

6
6
1
1
1
1
1
1
1

10 11
0
1
3 8
2
3 8
5 7
3
3 8
5 7
4 2
4
3 8
5 7
4 2
10 6
5
3 8
5 7
4 2
10 6
8 10
6
3 8
5 7
4 2
10 6
8 10
1 9
7
3 8
5 7
4 2
10 6
8 10
1 9
7 5
8
3 8
5 7
4 2
10 6
8 10
1 9
7 5
2 3
9
3 8
5 7
4 2
10 6
8 10
1 9
7 5
2 3
6 0

160
20
8
7
2
1
1
1
1
1

5 987
3
654 321
543 210
432 106
2
654 321
543 210
1
654 321
1
0 493
0

0
538184948
693625420
932738155
251798971

提示

最大可能的 $f(p)$ 值为 $2$，且 $S=\{[2,0,3,1], [1,3,0,2]\}$。

$p=[5, 0, 6, 1, 7, 2, 9, 4, 10, 3, 8]$ 应在所有测试用例中计入。

$p=[4, 9, 3, 8, 2, 7, 0, 5, 10, 1, 6]$ 应在所有测试用例中计入。

请确保输出的答案对 $10^9+7$ 取模。

计分（SCORING）： Input 5: $N=15$ Input 6: $N=2000$ Inputs 7-9: 对所有测试用例，约束 $p_0=\lfloor N/2\rfloor$ 出现。 Inputs 10-13: 对所有测试用例，存在某个约束 $p_i = j$，其中 $j$ 等于 $\lfloor N/2\rfloor$。 Inputs 14-20: 无额外限制。

题目来源：Benjamin Qi

标签: USACO|2024|Platinum

来源

USACO|2024|Platinum