CF2171G Sakura Adachi and Optimal Sequences

“真令人头疼……” —— 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$ 的值应按通常方式输出，不需要取模。

在第二个样例中，只需三步即可将 $a$ 变为 $b$，并且只有一种做法，具体为： - 对 $a_1$ 加 $1$，得到 $a = [2, 1]$。然后将所有元素乘 $2$，得到 $a = [4, 2]$。然后对 $a_2$ 加 $1$，得到 $a = [4, 3]$。此时 $a = b$，达成目标。 可以证明，无法通过少于三次操作将 $a$ 变为 $b$。 由 ChatGPT 5 翻译