#PU1454. USACO 2024 December Contest, Platinum — Problem 3. Maximize Minimum Difference

    ID: 1340 传统题 4000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:dec24来源:usaco.orgscoring:equal_test_cases贪心枚举

USACO 2024 December Contest, Platinum — Problem 3. Maximize Minimum Difference

USACO 2024 December Contest, Platinum — Problem 3. Maximize Minimum Difference

题目描述

Note: The time limit for this problem is 4s, twice the default. Moo! You are given an integer NN (2≤N≤20002\le N\le 2000). Consider all permutations p=[p0,p1,…,pN−1]p=[p_0,p_1,\dots, p_{N-1}] of [0,1,2…,N−1][0,1,2\dots, N-1]. Let f(p)=min⁡i=0N−2∣pi−pi+1∣f(p)=\min_{i=0}^{N-2}|p_i-p_{i+1}| denote the minimum absolute difference between any two consecutive elements of pp. and let SS denote the set of all pp that achieve the maximum possible value of f(p)f(p). You are additionally given KK (0≤K≤N0\le K\le N) constraints of the form pi=jp_i=j (0≤i,j<N0\le i,j<N). Count the number of permutations in SS satisfying all

输入格式

The first line contains TT (1≤TN≤2⋅1041\le TN\le 2\cdot 10^4) and NN, meaning that you will need to solve TT independent test cases, each specified by a different set of constraints. Each test case starts with KK, followed by KK lines each containing ii and jj. It is guaranteed that The same ii does not appear more than once within the same test case. The same jj does not appear more than once within the same test case.

输出格式

For each test case, the answer modulo 109+710^9+7 on a separate line.

数据范围

(见题面原文)

样例

样例 1

3 4
0
1
1 1
2
0 2
2 3
2
0
1
The maximum possible value of $f(p)$ is $2$, and $S=\{[2,0,3,1], [1,3,0,2]\}$.

样例 2

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
$p=[5, 0, 6, 1, 7, 2, 9, 4, 10, 3, 8]$ should be counted for all test cases.

样例 3

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
$p=[4, 9, 3, 8, 2, 7, 0, 5, 10, 1, 6]$ should be counted for all test cases.

样例 4

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
Make sure to output the answer modulo $10^9+7$.