MVB's blog

Help with a Matrix Exponentation Problem
By MVB, history, 7 weeks ago, In English

Hello! I am very hard stuck with this problem form the 2024-2025 ICPC Brazil Subregional contest more specifically this.

We are given $$$N \le 10^{18}$$$ and $$$M \le 10^5$$$ pairs $$$(a_i \le 100, b_i \le 60)$$$ that we can choose any amount of time. For pair $$$i$$$ we can subtract $$$a_i$$$ form $$$N$$$ only if $$$N \% 2^{b_i} == 0$$$. Now we need to find all the different ways in which we can obtain $$$0$$$ doing these operations. (I recommend reading the statement in case I missed to specify smth.)

First it's pretty clear that we can construct a very basic dynamic programming solution that is we iterate for all numbers $$$i \le N$$$ and for each $$$i$$$ iterate over all pairs and check if $$$i \% 2^{b_j} == 0$$$ then $$$dp[i] += dp[i - a_j]$$$. This runs in $$$\mathcal{O}(N \times M)$$$.

There is also a speedup based on the fact that for a certain $$$i$$$ if there are let's say $$$cnt$$$ trailing zeros then $$$i$$$ can use all pairs with $$$b_j \le cnt$$$. So we can precompute $$$cnt[b][i]$$$ which means the number of pairs such that $$$a_j = i$$$ and have $$$b_j \le b$$$ in $$$\mathcal{O}(M \times 100)$$$ and then we can compute the answer using a generic linear recurrence based on our calculations. Overall complexity $$$\mathcal{O}((N + M) \times 100)$$$.

This is also not enough to enter our time limit. Now from our input restrictions it's pretty clear that we will need to use Matrix Exponentiation, the only problem here is that I do not see how we can do so based on the fact that we will need for each $$$i$$$ to see the number of trailing zeros. I have seen some solutions online, I did not understand how they compute the answer, so here I am asking for help.

Any similar problem(s), or hints even would be much appreciated. Thanks!

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

So your speedup is actually key to solving this problem. As we know, matrix exponentiation can be used to speedup linear recurrent dynamic programming.

Let's write out our matrix exponential:

$$$\underbrace{\begin{bmatrix} dp[i] \\ dp[i-1] \\ \vdots \\ dp[i-99] \end{bmatrix}}_{\textbf{DP}_i} = \underbrace{\begin{bmatrix} \text{cnt}[v_2(i)][1] & \text{cnt}[v_2(i)][2] & \text{cnt}[v_2(i)][3] & \cdots & \text{cnt}[v_2(i)][100] \\ 1 & 0 & 0 & \cdots & 0 \\ 0 & 1 & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \vdots \\ 0 & \cdots & 0 & 1 & 0 \end{bmatrix}}_{A_{v_2(i)}} \underbrace{\begin{bmatrix} dp[i-1] \\ dp[i-2] \\ \vdots \\ dp[i-100] \end{bmatrix}}_{\textbf{DP}_{i-1}}$$$

where $$$v_2(i)$$$ represents the number of trailing zeroes of $$$i$$$.

The problem here is that $$$A_{v_2(i)}$$$ is not the same everywhere! So we can't just use regular exponentiation by squaring. Let's see what happens if we multiply the matrices one by one instead, starting from 0 (which is the identity matrix).

$$$\begin{align} \textbf{DP}_1 &= A_0 \textbf{DP}_0 \\ \textbf{DP}_2 &= A_1 \textbf{DP}_1 = A_1 A_0 \textbf{DP}_0 \\ \textbf{DP}_3 &= A_0 \textbf{DP}_2 = A_0 A_1 A_0 \textbf{DP}_0 \\ \textbf{DP}_4 &= A_2 \textbf{DP}_3 = A_2 A_0 A_1 A_0 \textbf{DP}_0 \\ &\vdots \end{align}$$$

Let's look at powers of 2 minus 1.

In particular, let's look at 7.

Note that the binary numbers between $$$[5,7]$$$ look exactly the same as $$$[1,3]$$$. As in, their $$$v_2(i)$$$'s are the same! So since $$$\textbf{DP}_7$$$ is just the product of all $$$A_{v_2(i)}$$$ with $$$i \leqslant 7$$$, we can break it down as

$$$\textbf{DP}_7 = {\color{purple} {A_0 A_1 A_0}} \cdot A_2 \cdot {\color{purple} {A_0 A_1 A_0}} \textbf{DP}_0$$$

This should motivate a divide and conquer solution, namely let

$$$f(k) = \prod\limits_{i=1}^{2^k-1} A_{v_2(i)}$$$

then we have

$$$f(k) = f(k-1) \cdot A_{k-1} \cdot f(k-1)$$$

So, we can memoise $f$ and use it in computations. So now we know how to solve the power of 2 case. What about general $$$n$$$? At each step, we can find the largest power of 2 less than or equal to $$$n$$$, then find the solution up to there. Then, subtract $$$2^{v_2(n)}$$$ from $$$n$$$.

And repeat the process until $$$n$$$ reaches 0. Keep multiplying the output of $$$f$$$ this way in a cumulative product matrix, taking care to multiply from the left. Then at the end, multiply the finished product matrix with $$$[1,0,0,\dotsc,0]$$$ to get the final answer.

→ Reply