Smaller Averages

题目描述

Bessie 有两个长度为 $N$ 的数组（$1 \le N \le 500$）。第一个数组的第 $i$ 个元素为 $a_i$（$1 \le a_i \le 10^6$），第二个数组的第 $i$ 个元素为 $b_i$（$1 \le b_i \le 10^6$）。 Bessie 想要将两个数组都划分成若干个非空子数组，使得满足以下条件。 每个元素恰好属于 1 个子数组。 两个数组被划分成相同数量的子数组。设第一个数组和第二个数组被划分成的子数组数量为 $k$（即第一个数组恰好被划分成 $k$ 个子数组，第二个数组也恰好被划分成 $k$ 个子数组）。 对所有 $1 \le i \le k$，第一个数组从左数第 $i$ 个子数组的平均值小于等于第二个数组从左数第 $i$ 个子数组的平均值。 在满足约束的前提下，求她将两个数组划分为非空子数组的方案数，对 $10^9+7$ 取模。若两种方案的子数组数量不同，或存在某个元素属于不同的子数组，则认为两种方案不同。

输入格式

第一行包含 $N$。 下一行包含 $a_1,a_2,...,a_N$。 下一行包含 $b_1,b_2,...,b_N$。

输出格式

输出在满足约束的前提下，将两个数组划分为非空子数组的方案数，对 $10^9+7$ 取模。

2
1 2
2 2

2

3
1 3 2
2 2 2

3

5
2 5 1 3 2
2 1 5 2 2

1

7
3 5 2 3 4 4 1
5 3 5 3 3 4 1

140

提示

两种有效的方式为： 将第一个数组划分为 $[1],[2]$，将第二个数组划分为 $[2],[2]$。 将第一个数组划分为 $[1,2]$，将第二个数组划分为 $[2,2]$。 三种有效的方式为： 将第一个数组划分为 $[1,3],[2]$，将第二个数组划分为 $[2,2],[2]$。 将第一个数组划分为 $[1,3],[2]$，将第二个数组划分为 $[2],[2,2]$。 将第一个数组划分为 $[1,3,2]$，将第二个数组划分为 $[2,2,2]$。 唯一有效的方式是将第一个数组划分为 $[2],[5,1,3],[2]$，并将第二个数组划分为 $[2],[1,5],[2,2]$。 评分： 输入 5-6：$N \le 10$ 输入 7-9：$N \le 80$ 输入 10-17：$N \le 300$ 输入 18-20：$N \le 500$ 题目贡献：Alex Liang

标签: USACO|2024|Gold

来源

USACO|2024|Gold