logo AlgoBeat OnlineJudge
登录 注册

#215556. [CCPC 2025 哈尔滨站] Many Many Sequence Covering Problems

内存限制:512 MiB 时间限制:4000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

考虑以下两个问题:

在该问题中,初始会给出三个长度为 的非负整数序列 ,每次可以用 的代价选择区间 ,满足 的最小值不为 ,将 全部减去 ,目标是用最小的代价将 中的所有数变为

在 Sequence Covering Problems 的基础上,给出两个非负整数序列 ,现在可以做以下操作任意次:选择 ,花费 的代价让 增大 ,或花费 的代价让 增大 。在所有操作结束后,对操作后的 序列求解其 Sequence Covering Problems,设其答案为 ,花费的代价为 ,你需要最大化 的值,如果这个值可以是无限大,请输出 INF,否则请给出这个最大值。

现在你要解决

给出五个长度为 的残缺序列 ,规定若 ,则 的值已经给出,否则认为 的取值范围为 ,对于 序列同理。

你需要求出所有可能的情况下,其对应的 Many Sequence Covering Problems 的答案之和。由于答案可能是 INF,所以你需要分别给出,当答案不为 INF 时所有的答案之和,以及有多少种情况其对应的答案为 INF。由于答案可能很大,答案对 取模。

输入格式

输入第一行包含一个整数 (),表示序列的长度。

输入第二行包含 个整数 ()。

输入第三行包含 个整数 ()。

输入第四行包含 个整数 ()。

输入第五行包含 个整数 ()。

输入第六行包含 个整数 ()。

输出格式

输出只有一行,包含两个整数,分别表示当答案不为 INF 时,所有的答案之和对 取模后的值,对应的答案为 INF 的情况数对 取模后的值。

样例

样例输入 1

2
1 1
1 2
2 1
-1 -1
-1 -1

样例输出 1

8 12

样例输入 2

3
-1 -2 2
1 3 0
-3 0 -2
1 -3 0
1 3 3

样例输出 2

408 228