The only resource available on the internet regarding the application of matrix exponentiation to TWO-DIMENSIONAL dynamic programming problems is this :-

http://threads-iiith.quora.com/Solving-Dynamic-Programming-with-Matrix-Exponentiation

Though the author has covered the topic with nice examples, I have some doubts:-

1) Unlike solving linear recurrences (using matrix exponentiation), I cannot find any solid mathematics behind the steps (or how does it work mathematically) involved in this technique.

2) How are the base-states taken into account in this technique? After building the adjacency-matrix (as is explained in the quora-article), and exponentiating it, what all values do we have to sum up to get the final answer?

I am pretty vague about all these details so any help will be much appreciated.

How exactly is the square root decomposition of queries (also sometimes referred to as Mo's Algorithm), used for offline processing of queries? If possible, please explain with an example.

NOTE :- I've gone over this post, but it lacks in covering the topic with an example and complexity analysis properly.

Should a state in DP be viewed as

1) a description of current scenario (e.g. in knapsack problem -->I am on item 'i' with having filled the bag with 'j' units)

OR as

2) a separate sub-problem (e.g. in knapsack problem -->maximum value that can be attained with weight less than or equal to 'j' using items upto 'i' (first 'i' items) )

I have seen both the interpretations used many times and I would welcome some opinions regarding the same.

Problem --> Interesting Array (CF Round 275): Div.1/B or Div.2/D

Tourist's code : http://ideone.com/c5dTmY

In this problem, for every set bit in query, we set the corresponding bit for all the numbers in the given range. I can't understand how he's doing that by:

s[from[k]][j]++; s[to[k] + 1][j]--;

Also, for calculating the number of set bits for a given bit position, for a given range of numbers, he's made some sort of cumulative array. Please explain its construction:

bal += s[i][j]; a[i][j] = (bal > 0); sum[i + 1][j] = sum[i][j] + a[i][j];