Trails (Hard)
Contest: Helvetic Coding Contest 2024 online mirror (teams allowed, unrated)
Difficulty rating: 2200
Tags: dp, matrices

Harry Potter is hiking in the Alps surrounding Lake Geneva. In this area there are $$$m$$$ cabins, numbered 1 to $$$m$$$. Each cabin is connected, with one or more trails, to a central meeting point next to the lake. Each trail is either short or long. Cabin $$$i$$$ is connected with $$$s_i$$$ short trails and $$$l_i$$$ long trails to the lake.

Each day, Harry walks a trail from the cabin where he currently is to Lake Geneva, and then from there he walks a trail to any of the $$$m$$$ cabins (including the one he started in). However, as he has to finish the hike in a day, at least one of the two trails has to be short.

How many possible combinations of trails can Harry take if he starts in cabin 1 and walks for $$$n$$$ days?

Give the answer modulo $$$10^9 + 7$$$.

Input format:
The first line contains the integers $$$m$$$ and $$$n$$$.

The second line contains $$$m$$$ integers, $$$s_1, \dots, s_m$$$, where $$$s_i$$$ is the number of short trails between cabin $$$i$$$ and Lake Geneva.

The third and last line contains $$$m$$$ integers, $$$l_1, \dots, l_m$$$, where $$$l_i$$$ is the number of long trails between cabin $$$i$$$ and Lake Geneva.

We have the following constraints:

$$$0 \le s_i, l_i \le 10^3$$$.

$$$1 \le m \le 10^5$$$.

$$$1 \le n \le 10^9$$$.

Output format:
The number of possible combinations of trails, modulo $$$10^9 + 7$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
3 2
1 0 1
0 1 1

Example output:
18

Editorial:
Let $$$t_i := s_i + l_i$$$. The number of possible paths between cabin $$$i$$$ and cabin $$$j$$$ is $$$t_i t_j - l_i l_j$$$.
Let $$$\mathbf{v}_{k}$$$ be the vector whose $$$i$$$th entry is the number of paths that ends in cabin $$$i$$$ after walking for $$$k$$$ days. We then have $$$$$$ \mathbf{v}_0 = (1, 0, \dots, 0), $$$$$$ and $$$$$$ (\mathbf{v}_{k+1})_i = \sum_{j = 1}^{m} (t_i t_j - l_i l_j) (\mathbf{v}_{k})_j. $$$$$$ Let $$$A$$$ be the $$$(m \times m)$$$–matrix given by $$$$$$ A_{i,j} = t_i t_j - l_i l_j. $$$$$$ Then the equation for $$$\mathbf{v}_{k+1}$$$ can be rewritten as $$$$$$ \mathbf{v}_{k+1} = A \mathbf{v}_k. $$$$$$ Hence, $$$$$$ \mathbf{v}_n = A^n \mathbf{v}_0. $$$$$$
Now, observe that $$$A$$$ can be written as $$$A = BC$$$, where $$$B$$$ is the $$$(m \times 2)$$$–matrix $$$$$$ \begin{pmatrix} t_1 & l_1 \\ t_2 & l_2 \\ \vdots & \vdots \\ t_m & l_m \\ \end{pmatrix}, $$$$$$ and $$$C$$$ is the $$$(2 \times m)$$$–matrix $$$$$$ \begin{pmatrix} t_1 & t_2 & \cdots & t_m \\ -l_1 & -l_2 & \cdots & -l_m \\ \end{pmatrix}. $$$$$$ We now have $$$$$$ A^n = B (CB)^{n-1} C. $$$$$$ As $$$CB$$$ is a $$$(2\times 2)$$$–matrix, we can compute $$$(CB)^{n-1}$$$ in $$$\mathcal{O}(\log(n))$$$ time (see the solution in Trails (medium version) for an explanation of the matrix exponentiation algorithm). Finally, computing the expression $$$$$$ \mathbf{v}_n = B (CB)^{n-1} C \mathbf{v}_0 $$$$$$ takes $$$\mathcal{O}(m + \log(n))$$$ time (note: we need to multiply the expression from the right side; multiplying from the left would take $$$\mathcal{O}(m^2 + \log(n))$$$ time). The solution is $$$(\mathbf{v}_n)_1 + \dots + (\mathbf{v}_n)_m$$$.