足立正处于世代崩溃之中......结束了,呃,这个问题!是的,一定是这样……不管怎样,请帮她解决这个问题吧!
给定两个数组 $$$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$$$。
示例
输入复制
861 3 6 4 3 23 7 10 4 4 821 14 352 3 2 5 118 13 10 30 755 4 3 6 2100 125 231 113 10742 2 2 22 2 2 241 1 1 12 2 2 271 1 1 1 1 1 200000200000 200000 200000 200000 200000 200000 2000003542264 174876 441510641112 325241 995342
输出复制
17 8271163 112 28835 5678120 11 11199994 0803045 366998
注意
在第二个示例中,仅使用三个操作即可将 $$$a$$$ 转换为 $$$b$$$。只有一种方法可以做到这一点,即:
- 将 $$$1$$$ 添加到 $$$a_1$$$,得到 $$$a = [2, 1]$$$。然后将 $$$a$$$ 的所有元素加倍,得到 $$$a = [4, 2]$$$。然后将 $$$1$$$ 添加到 $$$a_2$$$,得到 $$$a = [4, 3]$$$。然后我们就可以根据需要得到 $$$a = b$$$。
可以证明,使用少于三个操作将 $$$a$$$ 转换为 $$$b$$$ 是不可能的。