当前没有测试数据。

USACO 2024 US Open Contest, Gold Problem 3: Smaller Averages

一、题目描述

1. 数组设定

Bessie has two arrays of length $N$ ($1\leq N\leq 500$). The $i$-th element of the first array is $a_{i}$ ($1\leq a_{i}\leq 10^{6}$) and the $i$-th element of the second array is $b_{i}$ ($1\leq b_{i}\leq 10^{6}$).

2. 分割要求

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 $k$ (i.e. the first array is split into exactly $k$ subarrays and the second array is split into exactly $k$ subarrays).
• For all $1\leq i\leq k$, the average of the $i$-th subarray on the left of the first array is less than or equal to the average of the $i$-th subarray on the left of the second array.

3. 任务

Count how many ways she can split both arrays into non-empty subarrays while satisfying the constraints modulo $10^{9}+7$. Two ways are considered different if the number of subarrays are different or if some element belongs in a different subarray.

二、输入格式

1. The first line contains $N$.
2. The next line contains $a_{1}, a_{2}, \cdots, a_{N}$.
3. The next line contains $b_{1}, b_{2}, \cdots, b_{N}$.

三、输出格式

Output the number of ways she can split both arrays into non-empty subarrays while satisfying the constraints modulo $10^{9}+7$.

四、样例输入输出

样例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

五、评分规则

1. Inputs 5 - 6: $N\leq 10$.
2. Inputs 7 - 9: $N\leq 80$.
3. Inputs 10 - 17: $N\leq 300$.
4. Inputs 18 - 20: $N\leq 500$.

六、题目来源

Problem credits: Alex Liang.