A5080 · [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$ 取模后的结果。 ## 说明/提示 ### 评分方式 对于每个测试点： - 正确回答所有测试数据的 $\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)。

输入格式

**本题包含多组测试数据。** 输入的第一行包含两个非负整数 $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

输出 #1

15 10
1 18
37 48

A5080 | [NOI2025] 序列变换

题目描述

输入格式

输出格式

输入输出样例

A5080 | $[NOI2025] 序列变换$