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.
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.