P13272 [NOI2025] 序列变换

给定两个长度为 $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$ 取模。** 本题包含两个小问，正确回答其中任意一个小问均可获得部分分数。具体评分规则请参见【评分方式】。

### 样例 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$。 ::cute-table{tuack} | 测试点编号 | $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](https://qoj.ac/contest/2315/problem/13080)。