math, matrix expontiation, polynomial multiplication, lagrange polynomial
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)
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 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
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
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.
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
Can be found here.
Can be found here.