#PU1427. USACO 2024 US Open Contest, Gold — Problem 3. Smaller Averages

    ID: 1665 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:open24来源:usaco.orgscoring:equal_test_cases动态规划

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 NN (1≤N≤5001 \le N \le 500). The ii-th element of the first array is aia_i (1≤ai≤1061 \le a_i \le 10^6) and the ii-th element of the second array is bib_i (1≤bi≤1061 \le b_i \le 10^6). 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 kk (i.e. the first array is split into exactly kk subarrays and the second array is split into exactly kk subarrays). For all 1≤i≤k1 \le i \le k, the average of the ii-th subarray on the left of the first array is less than or equal to the average of the ii-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 109+710^9+7. 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 NN. The next line contains a1,a2,...,aNa_1,a_2,...,a_N. The next line contains b1,b2,...,bNb_1,b_2,...,b_N.

输出格式

(见题面原文)

数据范围

Inputs 5-6: N≤10N \le 10 Inputs 7-9: N≤80N \le 80 Inputs 10-17: N≤300N \le 300 Inputs 18-20: N≤500N \le 500 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