06751. USACO·最大化最小差 未做

注意：本题的时间限制为 4 秒，通常限制的 2 倍。

哞！你被给定了一个整数 $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$ 和 $N$（$1\le TN\le 2\cdot 10^4$），表示你需要求解 $T$ 个独立的测试用例，每个测试用例指定一组不同的限制。

每个测试用例的第一行包含 $K$，以下 $K$ 行，每行包含 $i$ 和 $j$。输入保证

• 相同的 $i$ 在同一测试用例中不会出现超过一次。
• 相同的 $j$ 在同一测试用例中不会出现超过一次。

对于每个测试用例输出一行，包含答案模 $10^9+7$ 的余数。

【样例解释】

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

• 测试点 6：$N=2000$。

• 测试点 7-9：对于所有测试用例，均存在限制 $p_0=\lfloor N/2\rfloor$。

• 测试点 10-13：对于所有测试用例，均存在某个限制 $p_i=j$，其中 $j$ 等于 $\lfloor N/2\rfloor$。

• 测试点 14-20：没有额外限制。

【数据规模与约定】

• 测试点 5：$N=15$。

• 测试点 6：$N=2000$。

• 测试点 7-9：对于所有测试用例，均存在限制 $p_0=\lfloor N/2\rfloor$。

• 测试点 10-13：对于所有测试用例，均存在某个限制 $p_i=j$，其中 $j$ 等于 $\lfloor N/2\rfloor$。

• 测试点 14-20：没有额外限制。

供题：Benjamin Qi