负责人

• SleepingCup

题目描述

给定两个长度为 $n$ 的整数序列 $B = [b_1, \ldots, b_n]$，$C = [c_1, \ldots, c_n]$。对于长度为 $n$ 的非负整数序列 $D = [d_1, \ldots, d_n]$，设 $S(D)$ 为所有满足 $d_i = 0$ 的下标 $i$ 的集合，定义 $f(D) = \sum_{i \in S(D)} b_i$，$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$ 取模。

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

样例

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$。

【样例 2】

见选手目录下的 sequence/sequence2.in 与 sequence/sequence2.ans。

该样例满足测试点 $3,4$ 的约束条件。

【样例 3】

见选手目录下的 sequence/sequence3.in 与 sequence/sequence3.ans。

该样例满足测试点 $5,6$ 的约束条件。

【样例 4】

见选手目录下的 sequence/sequence4.in 与 sequence/sequence4.ans。

该样例满足测试点 $7$ 的约束条件。

【样例 5】

见选手目录下的 sequence/sequence5.in 与 sequence/sequence5.ans。

该样例满足测试点 $11,12$ 的约束条件。

【样例 6】

见选手目录下的 sequence/sequence6.in 与 sequence/sequence6.ans。

该样例满足测试点 $16\sim 18$ 的约束条件。

【数据范围】

设 $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$。

测试点编号	$n \leq$	$N \leq$	特殊性质
$1, 2$	$8$	$10^2$	无
$3, 4$	$200$	$400$	B
$5, 6$			无
$7$	$500$	$10^3$	A
$8 \sim 10$			B
$11, 12$			无
$13$	$3\,500$	$3 \times 10^4$	A
$14, 15$			B
$16 \sim 18$			无
$19, 20$	$5\,000$	$4 \times 10^4$

• 特殊性质 A：保证 $A_1 = A_2 = \cdots = A_n = 1$。
• 特殊性质 B：保证对于所有 $1 \leq i \leq n$，$A_i$ 均在 $[1, 10^9]$ 中 独立均匀随机 生成。

【评分方式】

对于每个测试点：

• 正确回答所有测试数据的 $\max_{D \in T(A)} f(D)$，可获得该测试点 $40\%$ 的分数；
• 正确回答所有测试数据的 $\sum_{D \in T(A)} g(D)$ 对 $1,000,000,007$ 取模后的结果，可获得该测试点 $60\%$ 的分数。

注意：即使选手仅回答了其中一个问题，也需要按照输出格式输出两个整数，分别对应两个问题的答案。

附加文件来自于 QOJ。