#PU1454. USACO 2024 December Contest, Platinum — Problem 3. Maximize Minimum Difference
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 (). Consider all permutations of . Let denote the minimum absolute difference between any two consecutive elements of . and let denote the set of all that achieve the maximum possible value of . You are additionally given () constraints of the form (). Count the number of permutations in satisfying all
输入格式
The first line contains () and , meaning that you will need to solve independent test cases, each specified by a different set of constraints. Each test case starts with , followed by lines each containing and . It is guaranteed that The same does not appear more than once within the same test case. The same does not appear more than once within the same test case.
输出格式
For each test case, the answer modulo 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$.