Palindrome-less Arrays cf-1140E

 Consider a -1 -1 ...ltimes... -1 -1 b

You need to find the no. of arrays in which no two consecutive elements are equal.

So first if you assign the value to the lth "-1" element i.e. element before b, obviously you can assign all the values to it from 1 to k, except b. You can't assign b to it because no two consecutive elements should be equal. So there are (k-1) ways in which you can assign the value to lth "-1" element.

Now I hope you know the meaning of cntSame(l), and cntDiff(l).

To calculate cntSame(l), consider what happens when a=b.

Suppose you assign value to p to the lth "-1" element. Obviously, p!=b.

Since a=b, therefore p!=a. So, remaining number of values will be (k-1) i.e. except a(or b, since a=b). Therefore cntSame(l) = (k-1)*cntDiff(l-1)

To calculate cntDiff(l), consider what happens when a!=b.

Suppose you assign value to p to the lth "-1" element. Obviously, p!=b.

Since a!=b, You can either assign p=a or p!=a. There will be exactly one case to assign p=a and (k-2) cases to assign p!=a. (k-2 because you cannot also assign p=b)

Therefore cntDiff(l) = cntSame(l-1) + (k-2)*cntDiff(l-1)