CFCF2171G.Sakura Adachi and Optimal Sequences

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

“真令人头疼……”

—— 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$ 的值应按通常方式输出，不需要取模。

输入输出样例

输入#1

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

输出#1

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$ 。

首页