CF2171G.Sakura Adachi and Optimal Sequences

"What a pain..."

— Hougetsu Shimamura

Adachi is in the middle of a generational crashout... over, uh, this problem! Yep, that's definitely it... anyways, please help her solve it!

You are given two arrays $a$ and $b$ of length $n$ ($1\leq a_i\leq b_i$).

In one operation, you may either:

• choose an index $i$ ($1\leq i\leq n$) and set $a_i := a_i + 1$, or
• double all elements of $a$.

Let $x$ denote the minimum number of operations needed to make $a = b$. Two arrays $a$ and $b$ of length $n$ are considered equal if $a_i = b_i$ for all $1\leq i\leq n$.

Find the value of $x$. Additionally, count the number of sequences of operations that make $a = b$ using exactly $x$ operations. Two such sequences of operations are considered different if, for any $1\leq j\leq x$, the $j$-th operation of each sequence differs (either in the type of operation selected or the index chosen, if applicable).

Since the number of sequences may be large, output it modulo ${\color{red}{10^6+3}}$. Note that $10^6+3$ is a prime number.

“真是麻烦啊……”

—— 望月志村

安达正陷入一代人的崩溃……原因嘛，呃，就是这道题！没错，肯定就是它了……总之，请帮她解决这个问题吧！

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

每次操作你可以执行以下两种之一：

• 选择一个下标 $i$（$1\leq i\leq n$），并将 $a_i$ 替换为 $a_i + 1$；或者
• 将数组 $a$ 的所有元素翻倍（即对每个 $i$，令 $a_i := 2 \cdot a_i$）。

记 $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$ 步操作不同（操作类型不同，或在同为第一类操作时所选下标 $i$ 不同），则认为这两个操作序列不同。

由于方案数可能很大，请将该数目对 ${\color{red}{10^6+3}}$ 取模后输出。注意：$10^6+3$ 是一个质数。

The first line contains a single integer $t$ ($1\leq t\leq 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($2\leq n\leq 2\cdot 10^5$).

The second line of each test case contains $n$ integers, $a_1, a_2, \dots, a_n$ ($1\leq a_i\leq 10^6$).

The third line of each test case contains $n$ integers, $b_1, b_2, \dots, b_n$ ($a_i\leq b_i\leq 10^6$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

第一行包含一个整数 $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$。

For each test case, output two integers, the value of $x$, and the number of sequences of operations that make $a = b$ using exactly $x$ operations, modulo $10^6+3$. The value of $x$ should be printed exactly; that is, it should not be taken modulo $10^6 + 3$.

对于每个测试用例，输出两个整数：$x$ 的值，以及恰好使用 $x$ 次操作使得 $a = b$ 的操作序列数量（对 $10^6+3$ 取模）。$x$ 的值应原样输出；即，不应对其取模 $10^6 + 3$。

In the second sample, it is possible to convert $a$ into $b$ using only three operations. There is only one way to do so, namely:

• Add $1$ to $a_1$, yielding $a = [2, 1]$. Then double all elements of $a$, yielding $a = [4, 2]$. Then add $1$ to $a_2$, yielding $a = [4, 3]$. Then we have that $a = b$, as desired.

It can be shown that it is impossible to convert $a$ into $b$ using fewer than three operations.

在第二个样例中，仅需三次操作即可将 $a$ 转换为 $b$。实现该转换的唯一方式如下：

• 将 $a_1$ 加 $1$，得到 $a = [2, 1]$；然后将 $a$ 的所有元素乘以 $2$，得到 $a = [4, 2]$；再将 $a_2$ 加 $1$，得到 $a = [4, 3]$。此时即有 $a = b$，符合要求。

可以证明：无法用少于三次操作将 $a$ 转换为 $b$。