题目描述

“真令人头疼……”

—— Hougetsu Shimamura

Adachi 正在为一道世代传承的难题抓耳挠腮……呃，对，就是这道题！反正，请你帮她解决吧！

你有两个长度为 $n$ 的数组 $a$ 和 $b$，满足 $1\leq a_i\leq b_i$。

每次操作，你可以：

• 选择一个下标 $i$（$1 \leq i \leq n$），令 $a_i := a_i + 1$，或者
• 使 $a$ 的所有元素都乘以 $2$。

记 $x$ 为将 $a$ 变为 $b$ 所需的最少操作次数。长度为 $n$ 的两个数组 $a$ 和 $b$，当且仅当对于所有 $1 \leq i \leq n$ 都有 $a_i = b_i$ 时，认为 $a = b$。

求 $x$ 的值。此外，计算用恰好 $x$ 次操作将 $a$ 变为 $b$ 的不同操作序列数量。若对于任意 $1 \leq j \leq x$，两条操作序列第 $j$ 步所选的操作类型或下标不同，则认为这两条操作序列不同。

由于方案数可能很大，请将答案对 $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$ 的值应按通常方式输出，不需要取模。

样例

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$，并且只有一种做法，具体为：

• 对 $a_1$ 加 $1$，得到 $a = [2, 1]$。然后将所有元素乘 $2$，得到 $a = [4, 2]$。然后对 $a_2$ 加 $1$，得到 $a = [4, 3]$。此时 $a = b$，达成目标。

可以证明，无法通过少于三次操作将 $a$ 变为 $b$。

由 ChatGPT 5 翻译

来源

Codeforces 2171G，英文题名 Sakura Adachi and Optimal Sequences。