facebook hackercup round 3

When it is down to top 100, the competition is tough, as is the problem.

A. given a matrix of conflict M[10][10], M[i][j] = 1 if i and j conflict. Find count of valid numbers with length K or less. K can be 10^18. A number is valid if any two conflicting digits have two other digits between them.

I don't have a solution but here is some idea.

Let C[L][first][second]  be the count of numbers with length at most L and first digit and second digit, both first and second could be zero.

Then C[L][first][second] = sum of C[L-1][second][d] for d = 0 to 9, and first does not conflict with d. (We already know that second does not conflict with d or C[L-1][second][d] is zero)

This is a linear recurrence and since L could be 10^18, this hints to a solution using fast exponentiation. It would be an easy problem if we need only one digit separation, now it is two digits.

Update: watashi's solution, you can map [first][second], a 2d vector into 1d by using a*n+b as coordinator, then the rest is just like a linear recurrence with two dimensions, L, and pair of first and second. Everybody knows fastpow can do this.