← 返回题目列表

Codeforces · 2171/G

G. 樱花足立和最佳序列

中文机器翻译题面 查看原题
“好痛苦……”
— 岛村凤月

足立正处于世代崩溃之中......结束了,呃,这个问题!是的,一定是这样……不管怎样,请帮她解决这个问题吧!

给定两个数组 $$$a$$$ 和 $$$b$$$,长度为 $$$n$$$ ($$$1\leq a_i\leq b_i$$$)。

在一次操作中,您可以:

  • 选择索引 $$$i$$$ ($$$1\leq i\leq n$$$) 并设置 $$$a_i := a_i + 1$$$,或者
  • 将 $$$a$$$ 的所有元素加倍。

让 $$$x$$$ 表示使 $$$a = b$$$ 所需的最少操作数。如果对于所有 $$$1\leq i\leq n$$$,$$$a_i = b_i$$$,则长度为 $$$n$$$ 的两个数组 $$$a$$$ 和 $$$b$$$ 被视为相等。

求 $$$x$$$ 的值。此外,计算使用 $$$x$$$ 操作使 $$$a = b$$$ 的操作序列的数量。如果对于任何 $$$1\leq j\leq x$$$,每个序列的第 $$$j$$$ 操作不同(选择的操作类型或选择的索引,如果适用),则认为两个这样的操作序列不同。

由于序列数量可能很大,因此将其对 $$${\color{red}{10^6+3}}$$$ 取模输出。请注意 $$$10^6+3$$$ 是素数。

输入

第一行包含一个整数 $$$t$$$ ($$$1\leq t\leq 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2\leq n\leq 2\cdot 10^5$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数,$$$a_1, a_2, \dots, a_n$$$ ($$$1\leq a_i\leq 10^6$$$)。

每个测试用例的第三行包含 $$$n$$$ 整数,$$$b_1, b_2, \dots, b_n$$$ ($$$a_i\leq b_i\leq 10^6$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,输出两个整数、$$$x$$$ 的值,以及使用 $$$x$$$ 运算使 $$$a = b$$$ 的运算序列数,以 $$$10^6+3$$$ 为模。 $$$x$$$ 的值应该准确打印;也就是说,应该 不 取模 $$$10^6 + 3$$$。

示例

输入
复制

8
6
1 3 6 4 3 2
3 7 10 4 4 8
2
1 1
4 3
5
2 3 2 5 1
18 13 10 30 7
5
5 4 3 6 2
100 125 231 113 107
4
2 2 2 2
2 2 2 2
4
1 1 1 1
2 2 2 2
7
1 1 1 1 1 1 200000
200000 200000 200000 200000 200000 200000 200000
3
542264 174876 441510
641112 325241 995342

输出
复制

17 827116
3 1
12 288
35 567812
0 1
1 1
1199994 0
803045 366998

注意

在第二个示例中,仅使用三个操作即可将 $$$a$$$ 转换为 $$$b$$$。只有一种方法可以做到这一点,即:

  • 将 $$$1$$$ 添加到 $$$a_1$$$,得到 $$$a = [2, 1]$$$。然后将 $$$a$$$ 的所有元素加倍,得到 $$$a = [4, 2]$$$。然后将 $$$1$$$ 添加到 $$$a_2$$$,得到 $$$a = [4, 3]$$$。然后我们就可以根据需要得到 $$$a = b$$$。

可以证明,使用少于三个操作将 $$$a$$$ 转换为 $$$b$$$ 是不可能的。