problem Link - Number of Routings
Problem Statement
It is well known that the routing algorithm used on the Internet is highly non-optimal. A “hop”, in Internet jargon, is a pair of nodes that are directly connected - by a cable or a microwave link or whatever. The number of hops that a packet may take in going from one node to another may be far more than the minimum required.
But the routing algorithm used by the Siruseri Network company is worse. Here, a packet sent from one node to another could even go through the same node twice or even traverse the same hop twice before it eventually finds its way to its destination. Sometimes a packet even goes through the destination more than once before it is considered “delivered”. Suppose the network in Siruseri consisted of the following nodes and cables:
There are 5 nodes and 8 cable links. Note that a pair of nodes may be connected by more than one link. These are considered to be different hops. All links are bidirectional. A packet from node 1 to node 5 may, for example, travel as follows: 1 to 2, 2 to 1, 1 to 3, 3 to 2, 2 to 1, 1 to 4, 4 to 5, 5 to 4, 4 to 5. This routing is of length 9 (the number of hops is the length of a given routing). We are interested in counting the number of different routings from a given source to a target that are of a given length.
For example, the number of routings from 1 to 2 of length 3 are 7. They are as follows (separated by ;): 1 to 2, 2 to 1 and 1 to 2; 1 to 3, 3 to 1 and 1 to 2; 1 to 4, 4 to $1 and 1 to 2; 1 to 5, 5 to 1 and 1 to 2; 1 to 4, 4 to 3 (via the left cable) and 3 to 2; 1 to 4, 4 to 3 ( via the right cable ) and 3 to 2; 1 to 2, 2 to 3 and 3 to 2.
You will be given a description of the network at Siruseri as well as a source, a target and the number of hops, and your task is to determine the number of routings from the source to the target which have the given number of hops. The answer is to be reported modulo 42373.
Approach
The problem can be solved using matrix exponentiation. Each element in the adjacency matrix represents the number of direct paths between nodes. By repeatedly multiplying this matrix with itself, we can compute the number of paths of increasing lengths. Specifically, if we raise the adjacency matrix to the power of k
, the element at position (i, j)
in the resulting matrix gives the number of paths of length k
from node i
to node j
. The algorithm begins by initializing a result matrix to store the intermediate computations and iteratively applies matrix multiplication. The base case is when k=1
, and the matrix remains unchanged. By decrementing k
in each iteration, the solution efficiently computes the number of paths using the binary exponentiation method to minimize the number of multiplications. At the end, the value at the position corresponding to the given source and target in the final matrix represents the result.
Time Complexity
Matrix multiplication takes O(n^3), and matrix exponentiation is performed in O(\log k). Thus, the overall time complexity is O(n^3 \cdot \log k).
Space Complexity
The space complexity is O(n^2) for storing the matrices.