# PROBLEM LINK:

# DIFFICULTY:

HARD

# PREREQUISITES:

math, matrix expontiation, polynomial multiplication, lagrange polynomial

# PROBLEM:

Given a directed graph of **N** vertices and integer **T**, each edge has two types of costs **F _{i}** and

**R**, for each

_{i}**i**,

**j**,

**k**count the number of paths of length

**T**which starts at vertex

**i**and end at same vertex, and the total cost of first type is

**j**(modulo

**N**) and the total cost of the second type is

**k**(modulo

**N**-1)

### SHORT EXPLANATION

let’s first find a way to mix both edge costs into a single cost in range **0** … **n * (n-1)-1** then we use matrix exponentiation where each cell is a polynomial of degree **n * (n-1)-1**, the coefficient **x ^{i}** of polynomial in cell in

**j**-th row and

**k**-th column tells us the number of ways to go from vertex

**j**to vertex

**k**in a route of length

**i**modulo

**n * (n-1)**

so let’s create matrix **A** of size **N*N** such that cell in **j**-th row and **k**-th column have polynomial equal to 0 if there’s no edge from vertex **j** to vertex **k**, otherwise it is equal to **x ^{i}** where

**i**is the length of that edge

Now all we need is to compute **A ^{T}** using matrix exponentiation then we are done, as you know fastest method to multiply two polynomials is

**O(m log m)**where

**m**is the degree of the biggest polynomial but this will be slow so we need to store polynomials in interpolation form of

**N * (N-1)**values in a way that support circular convolution

### EXPLANATION

## Changing double costs of an edge into single cost

first thing to do is to find a way to change from double costs into a single cost **L _{i}**, this cost should satisfy

**L**=

_{i}**F**(mod

_{i}**N**) and

**L**=

_{i}**R**(mod

_{i}**N-1**), and it should be in range [0,N*(N-1)-1], this value

**L**always exists and unique in that range since

_{i}**N-1**and

**N**are coprimes, to find this value:

since **L _{i}** =

**F**(mod

_{i}**N**) then

**L**should be of form

_{i}**K*N+F**, let’s substitute it in

_{i}**L**=

_{i}**R**(mod

_{i}**N-1**) so we have

**K*N+F _{i}** =

**R**(mod

_{i}**N-1**)

**K** = **R _{i}**-

**F**(mod

_{i}**N-1**)

so **K** should be equal to (**R _{i}**-

**F**) mod

_{i}**N-1**

## Transformation matrix

Let’s create a matrix **A** of **N** * **N** cells such that cell in **j**-th row and **k**-th column have polynomial equal to 0 if there’s no edge from vertex **j** to vertex **k**, otherwise it is equal to **x ^{i}** where

**i**is the length of that edge.

now **A ^{T}** will give us the information we need, cell

**i**-th row and

**j**-th column will give us a polynomial of degree

** such that its coefficient of*

*N*(N-1)-1**x**will tell us the number of paths from vertex

^{k}**i**to

**j**of length

**k**(modulo

**N * (N-1)**)

how to compute **A ^{T}**? if we used

**O(N^3)**matrix multiplication algorithm and

**O(M log M)**FFT polynomial multiplication algorithm (where

**M**is degree of polynomial which is

**N * (N-1)**), then we will have

**O(N^5 log N log T)**solution which is so slow specially with the hight constant factor from FFT algorithm so we need a faster method.

## Faster multiplication method

actually we can make polynomial multiplication faster if we store polynomials in other way than the set of coefficient values, a polynomial of degree **N * (N-1)-1** can be uniquely determined by interpolation of **N * (N-1)** points, usually it’s fine to choose any **N * (N-1)** points but since in our case our polynomial multiplication should be circular (i.e. if exponent of some **X** became bigger or equal **N * (N-1)** then we should take the exponent modulo **N * (N-1)**)

for this reason we have to choose **N * (N-1)** points carefully, now let **w** be an integer such that **w^(N * (N-1)) = 1 (mod 1163962801)**, then in each cell of transformation matrix we store those **N * (N-1)** values

**P(w ^{0}), P(w^{1}), P(w^{2}), … P(w^{N * (N-1)-1})**

where **P** is the polynomial in that cell, now to multiply two polynomials **A** and **B** we just calculate **N * (N-1)** new points which are

**A(w ^{0}) * B(w^{0}), A(w^{1}) * B(w^{1}), A(w^{2}) * B(w^{2}), … A(w^{N * (N-1)-1}) * B(w^{N * (N-1)-1})**

and this is **O(N * (N-1))** instead of **O(N * (N-1) log (N * (N-1)))**, now we just need to restore coefficients of polynomials on the diagonal of **A ^{T}**, which can be done using lagrange interpolation.

## Lagrange Interpolation

say we have **N** points (**X_{1},**Y _{1}**), (**X

_{2},

**Y**) … (**X

_{2}_{N},

**Y**)

_{N}and we want to find a polynomial which passes through all these points, it can be done in the following way.

let **L _{i}(X)** be polynomial such that it returns zero on all

**X**except when

_{j}**i=j**it returns non-zero value

it’s easy to see that **L _{i}(X) = (X-X_{1})(X-X_{2}) … (X-X_{i-1})(X-X_{i+1})…(X-X_{N})**

now say **P** is the required polynomial then

**P(X) = Y _{1} * L_{1}(X) / L_{1}(X_{1}) + Y_{2} * L_{2}(X) / L_{2}(X_{2}) … Y_{N} * L_{N}(X) / L_{N}(X_{N})**

now we extract **P(X)** to get the desired coefficients

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.