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_{i}, 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 N1) SHORT EXPLANATIONlet's first find a way to mix both edge costs into a single cost in range 0 ... n * (n1)1 then we use matrix exponentiation where each cell is a polynomial of degree n * (n1)1, the coefficient x^{i} of polynomial in cell in jth row and kth column tells us the number of ways to go from vertex j to vertex k in a route of length i modulo n * (n1) so let's create matrix A of size N*N such that cell in jth row and kth 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 * (N1) values in a way that support circular convolution EXPLANATIONChanging double costs of an edge into single costfirst 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_{i} (mod N) and L_{i} = R_{i} (mod N1), and it should be in range [0,N*(N1)1], this value L_{i} always exists and unique in that range since N1 and N are coprimes, to find this value: since L_{i} = F_{i} (mod N) then L_{i} should be of form K*N+F_{i}, let's substitute it in L_{i} = R_{i} (mod N1) so we have K*N+F_{i} = R_{i} (mod N1) K = R_{i} F_{i} (mod N1) so K should be equal to (R_{i} F_{i}) mod N1 Transformation matrixLet's create a matrix A of N * N cells such that cell in jth row and kth 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 ith row and jth column will give us a polynomial of degree N*(N1)1 such that its coefficient of x^{k} will tell us the number of paths from vertex i to j of length k (modulo N * (N1)) 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 * (N1)), 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 methodactually we can make polynomial multiplication faster if we store polynomials in other way than the set of coefficient values, a polynomial of degree N * (N1)1 can be uniquely determined by interpolation of N * (N1) points, usually it's fine to choose any N * (N1) points but since in our case our polynomial multiplication should be circular (i.e. if exponent of some X became bigger or equal N * (N1) then we should take the exponent modulo N * (N1)) for this reason we have to choose N * (N1) points carefully, now let w be an integer such that w^(N * (N1)) = 1 (mod 1163962801), then in each cell of transformation matrix we store those N * (N1) values P(w^{0}), P(w^{1}), P(w^{2}), ... P(w^{N * (N1)1}) where P is the polynomial in that cell, now to multiply two polynomials A and B we just calculate N * (N1) 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 * (N1)1}) * B(w^{N * (N1)1}) and this is O(N * (N1)) instead of O(N * (N1) log (N * (N1))), now we just need to restore coefficients of polynomials on the diagonal of A^{T}, which can be done using lagrange interpolation. Lagrange Interpolationsay we have N points (X_{1},Y_{1}), (X_{2},Y_{2}) ... (X_{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_{j} except when i=j it returns nonzero value it's easy to see that L_{i}(X) = (XX_{1})(XX_{2}) ... (XX_{i1})(XX_{i+1})...(XX_{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 SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 12 Nov '16, 12:38

Seems like we're effectively still using the (numbertheoretic) DFT. The evaluation at points $w^i$ are ($n=N\cdot(N1)$) $$ P(w^i)=\sum_{j=0}^{n1}a_j w^{ij}$$ with the coefficients $a_i$ of the polynomial and $w$ a nth root of unity. So the evaluation and interpolation steps could be speeded up further using a fast number theoritic transform. answered 16 Nov '16, 19:17
