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.
It can be proved by induction. I won't write a full formal proof but here's an explanation of why this solution works.
If you construct the graph that is explained in the editorial, visiting a node means adding this letter to your final word. Thus, traversing $$$l-1$$$ edges constructs a word of length $$$l$$$.
Now you want to compute for each starting letter $$$u$$$ how many different ways can we traverse $$$l-1$$$ edges, and the final answer will be the summation of that for all starting letters.
Let's solve a simplified version of this problem, and it'll be easy to generalize. In how many different ways can we go from node $$$u$$$ to node $$$v$$$ traversing exactly $$$k$$$ edges, given adjacency matrix $$$adj$$$
Let $$$ans$$$ be a matrix of same dimensions as $$$adj$$$ such that $$$ans[u][v]$$$ contains the answer for our question for any 2 nodes $$$(u, v)$$$. In the beginning it'll be initialized with the adjacency matrix values and the value of $$$ans[u][v]$$$ will mean number of ways to go from $$$u$$$ to $$$v$$$ traversing exactly $$$1$$$ edge (obviously here it's gonna be either 1 if there's an edge between them or 0 if no edge). What we're trying to achieve is that if $$$ans[u][v]$$$ contains our answer for traversing exactly $$$k$$$ edges, then multiplying it once more by $$$adj$$$ will give us the answer for exactly $$$k+1$$$ edges.
The key to understand this is to observe how the value of the cell containing our answer $$$ans[u][v]$$$ changes when multiplying matrix $$$ans$$$ by matrix $$$adj$$$ once. The new value will be $$$Summation(ans[u][i] * adj[i][v])$$$ for all nodes $$$i$$$. You're multiplying number of ways to go from node $$$u$$$ to node $$$i$$$ using exactly $$$k$$$ edges with the number of ways to go from node $$$i$$$ to node $$$v$$$ using exactly 1 edge. Summing that for all nodes $$$i$$$ will get you number of ways to go from node $$$u$$$ to node $$$v$$$ using exactly $$$k + 1$$$ edges.
Back to your problem if you multiply matrix $$$ans$$$ by matrix $$$adj$$$ $$$l-2$$$ times. $$$ans[u][v]$$$ will contain the number of ways to create a word starting with letter $$$u$$$ and ending with letter $$$v$$$ traversing exactly $$$l-1$$$ edges. The answer will be summation of the whole $$$ans$$$ matrix.
Also, since $$$ans$$$ is initialized with $$$adj$$$, the base and transformation matrix are both the same you can just raise $$$adj$$$ matrix to the power of $$$l-1$$$ and get the same answer. You can use fast exponentiation and matrix multiplication to achieve the stated complexity
this trick is mentioned in this blog but not explained as detailed.
Also in this blog you'll find the same problem solved with another approach attacking it from a dynamic programming perspective.
If you still have any questions, feel free to ask.