#P6055. Mr. Fixer

    ID: 6424 传统题 1000ms 512MiB 尝试: 13 已通过: 1 难度: 9 上传者: 标签>CF2800省选/NOI-WQS 二分线性 DP滚动数组二分图建模交换论证

Mr. Fixer

题目描述

给定两个正整数序列 a1,…,ana_1,\ldots,a_n 和 b1,…,bmb_1,\ldots,b_m。定义 nn 行 mm 列矩阵 AA,其中 Ai,j=aibjA_{i,j}=a_i b_j。

构造一个 (n+1)(n+1) 行 tt 列的整数矩阵 BB,满足以下条件。

  • 1≤Bi,j≤m1\le B_{i,j}\le m。
  • 相邻两行的同一列不相等,即 Bi,j≠Bi+1,jB_{i,j}\ne B_{i+1,j}。
  • 每一行内的 tt 个元素两两不同。

在所有合法 BB 中,求下式的最小值。

$$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,tn,m,t。第二行 nn 个整数 a1,…,ana_1,\ldots,a_n。第三行 mm 个整数 b1,…,bmb_1,\ldots,b_m。

输出格式

输出一行一个整数,表示 f(A,B)f(A,B) 的最小值对 109+710^9+7 取模的结果。

样例 1

2 2 2
9 9
6 1
252

可取 BB 的三行依次为 (1,2),(2,1),(1,2)(1,2),(2,1),(1,2)。每次转移均覆盖两列,最小代价为 252252。

样例 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×1051\le n,m,t\le5\times10^5,1≤ai,bi≤1091\le a_i,b_i\le10^9,t≤mt\le m。

子任务 分值 附加限制
1 5 m=2m=2,n≤4n\le4,t≤3t\le3
2 m=t=2m=t=2
3 n,m,t≤10n,m,t\le10
4 15 n,m,t≤102n,m,t\le10^2
5 25 t=mt=m,n,m,t≤104n,m,t\le10^4
6 20 n,m,t≤104n,m,t\le10^4
7 25 无

原 PDF 题面