Help needed in matrix exponentiation problem

Revision en1, by acash, 2019-06-25 14:01:13

Problem link : PK and interesting Language

I read the editorial but I didn't find the proof of correctness in editorial. Can anyone explain with the recurrence,how the below logic is working thanks in advance.

Editorial:

Complexity(per query): O(z^3 log(l)) where z is the number of alphabets and l is the length of word.

Explanation: Suppose we have a graph having each english alphabet as a vertex. There is an edge between the ith and jth english alphabet if the entry a[i][j]=1, where a is the input matrix. Now each word in the language is simply a path from the starting alphabet to the ending alphabet. To calculate the numbers of words of length l ending at particular alphabet,we need to calculate total paths of length l-1 ending at that alphabet. This can be found by raising the adjancy matrix to the power l-1. The jth number in the ith row of this matrix gives the number of words of length l starting at character i and ending at character j. To find the total number of words ending at a particular alphabet take the sum of all the numbers in the jth column. #### History

Revisions Rev. Lang. By When Δ Comment
en1 acash 2019-06-25 14:01:13 1220 Initial revision (published)