A16548. 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$ 是一个质数。
—— 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$。
每个测试用例的第一行包含一个整数 $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$。
- 对 $a_1$ 加 $1$，得到 $a = [2, 1]$。然后将所有元素乘 $2$，得到 $a = [4, 2]$。然后对 $a_2$ 加 $1$，得到 $a = [4, 3]$。此时 $a = b$，达成目标。
可以证明，无法通过少于三次操作将 $a$ 变为 $b$。