题目描述
给定两个正整数序列 a1,…,an 和 b1,…,bm。定义 n 行 m 列矩阵 A,其中 Ai,j=aibj。
构造一个 (n+1) 行 t 列的整数矩阵 B,满足以下条件。
- 1≤Bi,j≤m。
- 相邻两行的同一列不相等,即 Bi,j=Bi+1,j。
- 每一行内的 t 个元素两两不同。
在所有合法 B 中,求下式的最小值。
$$f(A,B)=
\sum_{i=1}^{n}\sum_{j=1}^{t}
\sum_{k=\min(B_{i,j},B_{i+1,j})}^{\max(B_{i,j},B_{i+1,j})} A_{i,k}.$$
最内层求和包含两端。保证存在合法矩阵。
输入格式
第一行三个整数 n,m,t。第二行 n 个整数 a1,…,an。第三行 m 个整数 b1,…,bm。
输出格式
输出一行一个整数,表示 f(A,B) 的最小值对 109+7 取模的结果。
样例 1
2 2 2
9 9
6 1
252
可取 B 的三行依次为 (1,2),(2,1),(1,2)。每次转移均覆盖两列,最小代价为 252。
样例 2
10 10 10
2 8 10 10 10 2 5 8 9 3
2 1 5 2 10 7 8 9 10 6
8040
样例 3–6 见原题的 下发数据。
数据范围
1≤n,m,t≤5×105,1≤ai,bi≤109,t≤m。
| 子任务 |
分值 |
附加限制 |
| 1 |
5 |
m=2,n≤4,t≤3 |
| 2 |
m=t=2 |
| 3 |
n,m,t≤10 |
| 4 |
15 |
n,m,t≤102 |
| 5 |
25 |
t=m,n,m,t≤104 |
| 6 |
20 |
n,m,t≤104 |
| 7 |
25 |
无 |
原 PDF 题面