BIKE - Editorial

PROBLEM LINK:

Practice
Contest

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 Fi and Ri, for each 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 0n * (n-1)-1 then we use matrix exponentiation where each cell is a polynomial of degree n * (n-1)-1, the coefficient xi 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 xi where i is the length of that edge

Now all we need is to compute AT 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 Li, this cost should satisfy Li = Fi (mod N) and Li = Ri (mod N-1), and it should be in range [0,N*(N-1)-1], this value Li always exists and unique in that range since N-1 and N are coprimes, to find this value:

since Li = Fi (mod N) then Li should be of form K*N+Fi, let’s substitute it in Li = Ri (mod N-1) so we have

K*N+Fi = Ri (mod N-1)

K = Ri- Fi (mod N-1)

so K should be equal to (Ri- Fi) mod 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 xi where i is the length of that edge.

now AT will give us the information we need, cell i-th row and j-th column will give us a polynomial of degree N(N-1)-1* such that its coefficient of xk will tell us the number of paths from vertex i to j of length k (modulo N * (N-1))

how to compute AT? 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(w0), P(w1), P(w2), … P(wN * (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(w0) * B(w0), A(w1) * B(w1), A(w2) * B(w2), … A(wN * (N-1)-1) * B(wN * (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 AT, which can be done using lagrange interpolation.

Lagrange Interpolation

say we have N points (**X1,Y1), (**X2,Y2) … (**XN,YN)

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

let Li(X) be polynomial such that it returns zero on all Xj except when i=j it returns non-zero value

it’s easy to see that Li(X) = (X-X1)(X-X2) … (X-Xi-1)(X-Xi+1)…(X-XN)

now say P is the required polynomial then

P(X) = Y1 * L1(X) / L1(X1) + Y2 * L2(X) / L2(X2) … YN * LN(X) / LN(XN)

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

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

Seems like we’re effectively still using the (number-theoretic) DFT. The evaluation at points w^i are (n=N\cdot(N-1))

P(w^i)=\sum_{j=0}^{n-1}a_j w^{ij}

with the coefficients a_i of the polynomial and w a n-th root of unity. So the evaluation and interpolation steps could be speeded up further using a fast number theoritic transform.

Hmm. Then we need to do composite size dft, since the polynomial degree is n * (n - 1) - 1. Right?