#PU1427. USACO 2024 US Open Contest, Gold — Problem 3. Smaller Averages
USACO 2024 US Open Contest, Gold — Problem 3. Smaller Averages
USACO 2024 US Open Contest, Gold — Problem 3. Smaller Averages
题目描述
Bessie has two arrays of length (). The -th element of the first array is () and the -th element of the second array is (). Bessie wants to split both arrays into non-empty subarrays such that the following is true. Every element belongs in exactly 1 subarray. Both arrays are split into the same number of subarrays. Let the number of subarrays the first and second array are split into be (i.e. the first array is split into exactly subarrays and the second array is split into exactly subarrays). For all , the average of the -th subarray on the left of the first array is less than or equal to the average of the -th subarray on the left of the second array. Count how many ways she can split both arrays into non-empty subarrays while satisfying the constraints modulo . Two ways are considered different if the number of subarrays are different or if some element belongs in a different subarray.
输入格式
The first line contains . The next line contains . The next line contains .
输出格式
(见题面原文)
数据范围
Inputs 5-6: Inputs 7-9: Inputs 10-17: Inputs 18-20: Problem credits: Alex Liang
样例
样例 1
2
1 2
2 2
2
The two valid ways are:
Split the first array into $[1],[2]$ and the second array into
$[2],[2]$.
Split the first array into $[1,2]$ and the second array into
$[2,2]$.
样例 2
3
1 3 2
2 2 2
3
The three valid ways are:
Split the first array into $[1,3],[2]$ and the second array into
$[2,2],[2]$.
Split the first array into $[1,3],[2]$ and the second
array into $[2],[2,2]$.
Split the first array into $[1,3,2]$ and the
second array into $[2,2,2]$.
样例 3
5
2 5 1 3 2
2 1 5 2 2
1
The only valid way is to split the first array into $[2],[5,1,3],[2]$ and the
second array into $[2],[1,5],[2,2]$.
样例 4
7
3 5 2 3 4 4 1
5 3 5 3 3 4 1
140