← 返回题目
题库练习 「NOI2025」序列变换
← 上一题 下一题 →

A6754 | 「NOI2025」序列变换

来源NOI
时间限制6s
内存限制1024MB
通过 / 提交0/0

题目描述

给定两个长度为 $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$ 取模后的结果。

输入格式

从文件 sequence.in 中读入数据。

**本题包含多组测试数据。**

输入的第一行包含两个非负整数 $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$。

输出格式

输出到文件 sequence.out 中。

对于每组测试数据，仅输出一行，其中包含两个整数，分别表示 $\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
C++ 编辑器
输入
输出