This problem was asked in recent CodeNation Online Test — Please give your solution idea to it
Given A,B,C — Count the number of valid arrays of size "A"; such that each number of the array is in the range [1,C]; and no subarray of length > B exists in the valid array such that all elements of that subarray are equal
1<=A<=10^9
1<=B<=50
1<=C<=10^5
A = 3
B = 1
C = 3
Output — 12
[121], [123], [131], [132], [213], [212], [231], [232], [312], [313], [321], [323] are all valid arrays.
Idea = Valid Arrays = Total — Invalid arrays = Counting of Invalid Arrays is easier than valid arrays as far as I can conclude.
Auto comment: topic has been updated by LovesProgramming (previous revision, new revision, compare).
This has been discussed already in a blog earlier if I'm not wrong.
Solution from the blog
This is Matrix Exponentiation