2171G. Sakura Adachi and Optimal Sequences

bitmasks, combinatorics, greedy, math, 2000

https://codeforces.com/problemset/problem/2171/G

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 𝑎 and 𝑏 of length 𝑛 (1≤𝑎𝑖≤𝑏𝑖).

In one operation, you may either:

choose an index 𝑖 (1≤𝑖≤𝑛) and set 𝑎𝑖:=𝑎𝑖+1, or
double all elements of 𝑎.

Let 𝑥 denote the minimum number of operations needed to make 𝑎=𝑏. Two arrays 𝑎 and 𝑏 of length 𝑛 are considered equal if 𝑎𝑖=𝑏𝑖for all 1≤𝑖≤𝑛.

Find the value of 𝑥. Additionally, count the number of sequences of operations that make 𝑎=𝑏 using exactly 𝑥 operations. Two such sequences of operations are considered different if, for any 1≤𝑗≤𝑥, the 𝑗-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 106+3. Note that 106+3 is a prime number.

Input

The first line contains a single integer 𝑡 (1≤𝑡≤104) — the number of test cases.

The first line of each test case contains a single integer 𝑛 (2≤𝑛≤2⋅105).

The second line of each test case contains 𝑛 integers, 𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤106).

The third line of each test case contains 𝑛 integers, 𝑏1,𝑏2,…,𝑏𝑛 (𝑎𝑖≤𝑏𝑖≤106).

It is guaranteed that the sum of 𝑛 over all test cases does not exceed 2⋅105.

Output

For each test case, output two integers, the value of 𝑥, and the number of sequences of operations that make 𝑎=𝑏 using exactly 𝑥operations, modulo 106+3. The value of 𝑥 should be printed exactly; that is, it should not be taken modulo 106+3.

Example

input

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

output

17 827116
3 1
12 288
35 567812
0 1
1 1
1199994 0
803045 366998

Note

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

Add 1 to 𝑎1, yielding 𝑎=[2,1]. Then double all elements of 𝑎, yielding 𝑎=[4,2]. Then add 1 to 𝑎2, yielding 𝑎=[4,3]. Then we have that 𝑎=𝑏, as desired.

It can be shown that it is impossible to convert 𝑎 into 𝑏 using fewer than three operations.

【尹显齐 2500011456 物理学院】

记 $N = 10^{6} + 3$ 首先，所有操作一定是由一些 $+ 1$ 和总体 $\times 2$ 形成的，由于每次 $+ 1$ 作用的元素不同，所以交换这些 $+ 1$ 的顺序就会产生不同的操作。
从正面直接寻找步数最少的操作方式是比较困难的，我们可以反向思考：我们可以对 $b$ 的某一个元素 $- 1$ ，或者在 $b$ 的所有元素为偶数时对所有元素除以 $2$ ，要求得到 $a$ 数组。最优的操作方式肯定是尽可能多，尽可能早的除以 $2$ ，所以我们在保证 $b_{i} \geq 2 a_{i}, \forall i$ 的情况下先对所有奇数 $- 1$ ，然后整体除以 $2$ ，当不满足前述条件时就只能一直减 $1$ 。在一个对 $a$ 数组的一些数 $+ 1$ 的过程中，假设对第 $i$ 个数需要加 $x_{i}$ ，那么这一过程的种类数为

\frac{(\sum_{i = 1}^{n} x_{i})!}{\prod_{i = 1}^{n} x_{i}!}

当 $\sum_{i = 1}^{n} x_{i} \geq N$ 时，上式对 $N$ 的余数为 $0$ ，否则我们需要计算。最后把所有的结果乘起来即得到总种类数量

python

MOD = 10**6+3
# 预计算1到MOD的阶乘和对应逆元
fact = [1] * (MOD)
inv_fact = [1] * (MOD)
for i in range(1,MOD):
    fact[i] = (fact[i-1] * i) % MOD
# 用费马小定理求逆元
inv_fact[MOD-1] = pow(fact[MOD-1],MOD-2,MOD)
for i in range(MOD-1,0,-1):
    inv_fact[i-1] = (inv_fact[i] * i) % MOD
# 定义计算单次+1过程的种类数的方法
def calc(a,total):
    res = fact[total]
    for val in a:
        res = (res * inv_fact[val]) % MOD
    return res
for _ in range(int(input())):
    n = int(input())
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))
    # 求解能乘以2的次数
    maxmul = 30
    for i in range(n):
        curmul = 0
        ai = a[i]
        while curmul < maxmul:
            if ai*2 <= b[i]:
                curmul += 1
                ai *= 2
            else:
                break
        maxmul = curmul
    step = 0# 总步数
    kinds = 0
    delta = []# 存b_i<2a_i时两者的差
    oper = [0]*maxmul
    for i in range(n):
        bi = b[i]
        for m in range(maxmul):
            oper[m] += bi%2# 是否需要-1？
            bi //= 2
        step += bi-a[i]
        delta.append(bi-a[i])
    kinds = calc(delta,step) if step < MOD else 0
    step += maxmul# 加上*2所需步数
    for i in range(maxmul):
        step += oper[i]
        if kinds:
            kinds = kinds * fact[oper[i]] % MOD
    print(step,kinds)

2171G. Sakura Adachi and Optimal Sequences ​

2171G. Sakura Adachi and Optimal Sequences