83072 - 序列变换

时间限制 6 秒 内存限制 128 MB

题目描述

给定两个长度为 $n$ 的整数序列 $B = [b_1, \ldots, b_n]$ ， $C = [c_1, \ldots, c_n]$ 。对于长度为 $n$ 的非负整数序列 $D = [d_1, \ldots, d_n]$ ，设 $S(D)$ 为所有满足 $di = 0 $的下标$ i $的集合，定义$ f(D) = \sum{i \in S(D)} bi $，$ g(D) = \prod{i \in S(D)} c_i $。特别地，若$ S(D) $为空，则$ f(D) = 0 $，$ g(D) = 1$。

小 L 有一个长度为 $n$ 的 正整数序列 $A = [a_1, \ldots, a_n]$ 。小 L 可以对序列 $A$ 做如下修改：

选择序列 $A$ 的两个相邻的下标 $i, j$ （即 $1 \leq i, j \leq n$ 且 $|i - j| = 1$ ），若 $a_i \leq a_j$ ，则将 $a_j$ 改为 $a_j - a_i$ ，同时将 $a_i$ 改为 $0$ 。

小 L 可以进行任意多次修改操作，也可以不进行任何修改。对于所有序列 $A$ 通过以上修改操作可以得到的序列 $D$ ，小 L 想求出 $f(D)$ 的最大值以及 $g(D)$ 之和，请你帮助他求出这两个值。形式化地，记 $T(A)$ 为序列 $A$ 通过以上修改操作可以得到的 所有序列的集合，你需要求出 $\max{D \in T(A)} f(D) $以及$ \sum{D \in T(A)} g(D) $。其中，由于$ \sum_{D \in T(A)} g(D) $可能较大，你只需要求出其对$ 1,000,000,007$ 取模后的结果。

输入

本题包含多组测试数据。

输入的第一行包含两个非负整数 $c, t$ ，分别表示测试点编号与测试数据组数。 $c = 0$ 表示该测试点为样例。

接下来依次输入每组测试数据，对于每组测试数据：

第一行包含一个正整数 $n$ ，表示序列长度。
第二行包含 $n$ 个正整数 $a_1, \ldots, a_n$ ，表示序列 $A$ 。
第三行包含 $n$ 个整数 $b_1, \ldots, b_n$ ，表示序列 $B$ 。
第四行包含 $n$ 个正整数 $c_1, \ldots, c_n$ ，表示序列 $C$ 。

输出

对于每组测试数据，仅输出一行，其中包含两个整数，分别表示 $\max{D \in T(A)} f(D) $以及$ \sum{D \in T(A)} g(D) $对$ 1,000,000,007$ 取模后的结果。注意： $\max_{D \in T(A)} f(D)$ 不需要对 $1,000,000,007$ 取模。

本题包含两个小问，正确回答其中任意一个小问均可获得部分分数。具体评分规则请参见【评分方式】。

样例

样例 1

输入

0 3
3
5 6 6
3 6 9
1 2 3
6
1 1 4 5 1 4
-1 1 -1 1 -2 2
1 1 1 1 1 1
8
4 2 4 2 2 2 4 4
-2 4 9 -3 4 8 7 8
1 1 1 1 1 1 1 1

输出

15 10
1 18
37 48

提示

样例 1 解释

该样例共包含三组测试数据。

对于第一组测试数据，可以得到以下 4 个序列：

$D = [5, 6, 6]$ ， $f(D) = 0$ ， $g(D) = 1$ ；
$D = [0, 1, 6]$ ， $f(D) = 3$ ， $g(D) = 1$ ；
$D = [5, 0, 0]$ ， $f(D) = 6 + 9 = 15$ ， $g(D) = 2 \times 3 = 6$ ；
$D = [0, 0, 5]$ ， $f(D) = 3 + 6 = 9$ ， $g(D) = 1 \times 2 = 2$ 。

故 $\max{D \in T(A)} f(D) = \max{0, 3, 15, 9} = 15 $，$ \sum{D \in T(A)} g(D) = 1 + 1 + 6 + 2 = 10$。

设 $N$ 为单个测试点内所有测试数据的 $n$ 的和。对于所有测试数据，保证：

$1 \leq t \leq 20$ ；
$1 \leq n \leq 5,000$ ， $N \leq 4 \times 10^4$ ；
对于所有 $1 \leq i \leq n$ ，均有 $1 \leq A_i \leq 10^9$ ；
对于所有 $1 \leq i \leq n$ ，均有 $-10^9 \leq B_i \leq 10^9$ ；
对于所有 $1 \leq i \leq n$ ，均有 $1 \leq C_i \leq 10^9$ 。

来源

NOI