Sakura Adachi and Optimal Sequences

We need minimize operations and count optimal operation sequences. The trick is to stop thinking about the operation order first. Pick the number of doublings, then everything becomes binary bookkeeping.

Fix the number of doublings

Suppose the sequence uses exactly $k$ double-all operations.

Every original value $a_i$ gets doubled $k$ times, so before considering increments it contributes

$a_i2^k$

to the final value. Therefore index $i$ still needs

$r_i=b_i-a_i2^k$

extra value.

If some $r_i<0$, then $k$ is impossible, because we already overshot $b_i$. There is no undo button.

Since $b_i\le 10^6$, we only need to try $k\le 19$ or so. Tiny.

How many increments are needed for fixed $k$?

An increment may happen:

• before all $k$ doublings, contributing $2^k$ to the final value;
• after one doubling, contributing $2^{k-1}$;
• ...
• after all doublings, contributing $1$.

So for index $i$, we must write $r_i$ as a sum of coins

$1,2,4,\dots,2^k,$

using as few coins as possible.

For powers of two, the greedy choice is optimal: use as many $2^k$ coins as possible, then use the binary representation of the remainder. Thus

$f_k(r_i)=\left\lfloor \frac{r_i}{2^k}\right\rfloor+\operatorname{popcount}(r_i\bmod 2^k).$

So the total operation count for this $k$ is

$k+\sum_{i=1}^n f_k(r_i).$

Try every feasible $k$, take the minimum value $x$.

The representation is unique

This matters for counting.

For $q<k$, the number of increments of index $i$ that contribute $2^q$ is exactly the $q$-th bit of $r_i$.

For $q=k$, the number is

$\left\lfloor \frac{r_i}{2^k}\right\rfloor.$

Why unique? If you had two $2^q$ coins for $q<k$, you could replace them with one $2^{q+1}$ coin and use fewer increments. So below the top coin, every count must be $0$ or $1$. The top coin $2^k$ can appear many times because there is no bigger allowed coin.

Counting operation sequences

The $k$ doublings split the sequence into $k+1$ gaps:

• increments before the first doubling;
• increments between doublings;
• increments after the last doubling.

The gap with $q$ future doublings contains exactly the increments that contribute $2^q$.

Let

$c_{i,q}$

be the required number of increments of index $i$ in that gap, and let

$S_q=\sum_i c_{i,q}.$

Inside that gap, the only freedom is the order of increment indices. Therefore the number of ways for that gap is the multinomial

$\frac{S_q!}{\prod_i c_{i,q}!}.$

The total number of sequences for this $k$ is the product over all gaps:

$\prod_{q=0}^{k}\frac{S_q!}{\prod_i c_{i,q}!}.$

The double operations themselves are fixed separators, so they do not add another factorial. Do not count random placements of doubles separately; the gaps already encode exactly where they are. Counting them again would be classic off-by-a-whole-combinatorics-problem nonsense.

Modulo issue

The modulo is

$p=10^6+3,$

which is prime.

Every individual $c_{i,q}$ is less than $p$, because all values are at most $10^6$. However, the sum $S_q$ can be much larger than $p$.

Since every $c_{i,q}<p$, none of the denominator factorials contains a factor of $p$. If $S_q\ge p$, then $S_q!$ does contain a factor of $p$, so the whole multinomial is $0$ modulo $p$. If $S_q<p$, we use the normal factorial formula.

So we precompute factorials and inverse factorials modulo $p$. For a gap:

• if $S_q\ge p$, the contribution is $0$;
• otherwise contribution is

$S_q!\prod_i (c_{i,q}!)^{-1}.$

For $q<k$, each $c_{i,q}$ is only $0$ or $1$, so the denominator is irrelevant. Only the top gap $q=k$ needs real denominator work.

Algorithm

For each test case:

1. Try all $k$ from $0$ while feasible.

2. Compute

   $r_i=b_i-a_i2^k.$

3. If any $r_i<0$, skip this $k$.

4. Compute operation count

   $k+\sum_i\left(\left\lfloor r_i/2^k\right\rfloor+\operatorname{popcount}(r_i\bmod 2^k)\right).$

5. Compute the number of optimal sequences for this fixed $k$ using gap multinomials.

6. Keep the minimum operation count; if multiple $k$ tie, add their counts modulo $p$.

Complexity:

$O(n\log 10^6)$

per test case in practice, since there are only about $20$ possible values of $k$. Across all tests, this is easily fine.