European Trip
Contest: SWERC 2021-2022 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Tags: dp, graphs, math, matrices

The map of Europe can be represented by a set of $$$n$$$ cities, numbered from $$$1$$$ through $$$n$$$, which are connected by $$$m$$$ bidirectional roads, each of which connects two distinct cities. A trip of length $$$k$$$ is a sequence of $$$k+1$$$ cities $$$v_1, v_2, \ldots, v_{k+1}$$$ such that there is a road connecting each consecutive pair $$$v_i$$$, $$$v_{i+1}$$$ of cities, for all $$$1 \le i \le k$$$. A special trip is a trip that does not use the same road twice in a row, i.e., a sequence of $$$k+1$$$ cities $$$v_1, v_2, \ldots, v_{k+1}$$$ such that it forms a trip and $$$v_i \neq v_{i + 2}$$$, for all $$$1 \le i \le k - 1$$$.

Given an integer $$$k$$$, compute the number of distinct special trips of length $$$k$$$ which begin and end in the same city. Since the answer might be large, give the answer modulo $$$998\,244\,353$$$.

Input format:
The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$3 \le n \le 100$$$, $$$1 \le m \le n(n - 1) / 2$$$, $$$1 \le k \le 10^4$$$) — the number of cities, the number of roads and the length of trips to consider.

Each of the following $$$m$$$ lines contains a pair of distinct integers $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le n$$$) — each pair represents a road connecting cities $$$a$$$ and $$$b$$$. It is guaranteed that the roads are distinct (i.e., each pair of cities is connected by at most one road).

Output format:
Print the number of special trips of length $$$k$$$ which begin and end in the same city, modulo $$$998\,244\,353$$$.

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

Note:
In the first sample, we are looking for special trips of length $$$2$$$, but since we cannot use the same road twice once we step away from a city we cannot go back, so the answer is $$$0$$$.

In the second sample, we have the following $$$12$$$ special trips of length $$$3$$$ which begin and end in the same city: $$$(1, 2, 4, 1)$$$, $$$(1, 3, 4, 1)$$$, $$$(1, 4, 2, 1)$$$, $$$(1, 4, 3, 1)$$$, $$$(2, 1, 4, 2)$$$, $$$(2, 4, 1, 2)$$$, $$$(3, 1, 4, 3)$$$, $$$(3, 4, 1, 3)$$$, $$$(4, 1, 3, 4)$$$, $$$(4, 3, 1, 4)$$$, $$$(4, 1, 2, 4)$$$, and $$$(4, 2, 1, 4)$$$.

Example input:
4 5 2
4 1
2 3
3 1
4 3
2 4

Example output:
0

Example input:
4 5 3
1 3
4 2
4 1
2 1
3 4

Example output:
12

Editorial:
Warm-up problem
Let us consider a related simpler problem first. Let $$$G$$$ be the graph that represents the cities and roads in the problem statement and let $$$A$$$ be its adjacency matrix. Suppose that instead of special trips we wanted to compute the number of distinct trips of length $$$k$$$ that begin and end in the same city. We can use an important property of the adjacency matrix $$$A$$$.
Lemma 1. For any $$$k \ge 1$$$, the $$$(i, \, j)$$$-th entry of the $$$k$$$-th power of $$$A$$$, $$$(A^k)_{ij}$$$ is equal to the number of trips of length $$$k$$$ that start at $$$i$$$ and end at $$$j$$$.
Proof. For $$$k = 1$$$ this is obvious from the definition of adjacency matrix. Assume the lemma holds for $$$k \geq 1$$$ and consider the matrix $$$A^{k+1} = A^k A$$$. By the inductive hypothesis, $$$(A^k)_{ij}$$$ is equal to the number of trips of length $$$k$$$ that start at $$$i$$$ and end at $$$j$$$. Now, the number of trips of length $$$k + 1$$$ between $$$i$$$ and $$$j$$$ is equal the number of trips of length $$$k$$$ from $$$i$$$ to some vertex $$$l$$$ adjacent to $$$j$$$, but this is given by $$$A^k A$$$, so the result follows by induction. $$$\blacksquare$$$
Thus, to compute the number of trips of length $$$k$$$ that begin and end in the same city we only need to compute $$$A^k$$$ and sum the elements in the diagonal of the matrix (this is called the trace of the matrix). To do so efficiently, we can use the binary exponentiation technique, which is summarized in the following recursive approach. Let $$$\displaystyle I = \begin{bmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{bmatrix}$$$ be the identity matrix. Then:
$$$$$$ A^k = \left\{ \begin{matrix} I & \mathrm{if} \; k = 0, \\ \left(A^{\frac{k}{2}}\right)^2 & \mathrm{if} \; k > 0 \; \mathrm{and} \; k \; \mathrm{even}, \\ \left(A^{\frac{k - 1}{2}}\right)^2 \cdot A & \mathrm{if} \; k > 0 \; \mathrm{and} \; k \; \mathrm{odd}. \end{matrix} \right. $$$$$$
Since we half the exponent in each step, this procedure takes $$$\mathcal O(\log k)$$$ steps. In each step we perform one or two matrix multiplications of two $$$n \times n$$$ square matrices, which takes (with the naïve algorithm) $$$\mathcal O(n^3)$$$ time. Overall this algorithm takes $$$\mathcal O(n^3 \log k)$$$ time to compute the answer.
Full problem
Let us now turn our attention back to the problem of computing the number of special trips that begin and end in the same city. There is no simple matrix whose powers correspond to special trips, but we can try to reason about how to describe these trips in terms of the adjacency matrix. Let $$$S^{(k)}$$$ be an $$$n \times n$$$ matrix whose $$$(i, \, j)$$$ entry is equal to the number of special trips of length $$$k$$$ that start in $$$i$$$ and end in $$$j$$$. Additionally, let $$$D$$$ be the degrees matrix, a diagonal matrix where $$$D_{ii}$$$ is equal to the degree of vertex $$$i$$$ in $$$G$$$.
Lemma 2. The following equalities hold.
• $$$S^{(1)} = A$$$.
• $$$S^{(2)} = A^2 - D$$$.
• $$$S^{(k)} = S^{(k - 1)} \cdot A - S^{(k - 2)} \cdot (D - I)$$$, for $$$k > 2$$$.
Proof. For $$$k = 1$$$ it is clear that the special trips of length $$$1$$$ are equivalent to edges in the graph. For $$$k = 2$$$, we know that $$$A^2$$$ corresponds to trips of length $$$2$$$. Special trips cannot use the same edge twice in a row, but $$$A^2$$$ ignores this constraint. However, the length 2 trips that use two edges in a row are exactly the trips that start in a vertex $$$v$$$, follow one of the $$$\deg(v)$$$ adjacent edges, where $$$\deg(v)$$$ is the degree of $$$v$$$, and then follow that same edge back. The number of such trips is given exactly by $$$D$$$, so by subtracting this matrix from the total number of trips of length $$$2$$$ we get $$$S^{(2)} = A^2 - D$$$.
Now consider $$$k \ge 3$$$. Note that $$$S^{(k - 1)} \cdot A$$$ is the number of trips of length $$$k$$$ that do not use the same road twice in a row, except maybe on the very last step. This is almost what we want, but we need to subtract the number of trips that do not use the same road twice in a row, except on the very last step. Applying a similar reasoning as in the $$$k = 2$$$ case, this is equal to the number of special trips of length $$$k - 2$$$ that end at some vertex $$$v$$$, then follow one of its $$$\deg(v)$$$ adjacent edges, and finally follow that same edge back. However, we do not need to count the edge that preceded getting to $$$v$$$, since that would lead to walking the same edge twice in the second to last step. The number of such trips is given by $$$S^{(k - 2)} \cdot (D - I)$$$, where $$$D - I$$$ is the "degree minus one" diagonal matrix. So the result follows. $$$\blacksquare$$$
We are still not done because it is not obvious how to solve this recurrence efficiently. Note that this is a linear recurrence, so we can use any linear recurrence solving technique. There are several ways of doing this, but let us consider a matrix exponentiation method. Consider the following block matrix:
$$$$$$ L = \begin{bmatrix} A & -(D - I)\\ I & 0 \end{bmatrix}. $$$$$$
Note that $$$L$$$ is a $$$2n \times 2n$$$ matrix. If we multiply it by some column vector we get:
$$$$$$ \begin{bmatrix} A & -(D - I)\\ I & 0 \end{bmatrix} \begin{bmatrix} S_1\\ S_2 \end{bmatrix} = \begin{bmatrix} A S_1 - (D - I) S_2 \\ S_1 \end{bmatrix}. $$$$$$
In particular, this has the exact form of the recurrence in Lemma 2, which means that the product of $$$L^{k-2}$$$ by a column vector with entries $$$S^{(2)}$$$ and $$$S^{(1)}$$$ will result in a column vector with entries $$$S^{(k)}$$$ and $$$S^{(k - 1)}$$$. To compute $$$L^{k-2}$$$ we can use the same binary exponentiation method from the first section, so overall this method takes $$$\mathcal O(n^3 \log k)$$$ time.