PROBLEM LINK:
Editorialist: Karan Aggarwal
DIFFICULTY:
EASY
PREREQUISITES:
MATHS, MODULAR EXPONENTIATION
PROBLEM:
Given infinite supply of K different types of explosives you have to find the number of ways to place the explosives in a grid of size N*2 such that :
Type[i][0] != Type[i][1],
Type[i][j] != Type[i+1][j]
EXPLANATION:
There are K*(K-1) ways to fill the first row.
And for any other row, there are exactly (K-2)*(K-2) + 1*(K-1) ways to fill the row.
This can be calculated as follows.
Let say we are filling the ith row, and the (i-1)th row is such that Type[i-1][0] = a, Type[i-1][1] = b.
Now Type[i][0] can be any other color c different from a and b, hence there are (K-2) ways to chose c, and then Type[i][1] can be any color other than b and c, so again (K-2) choices. Hence (K-2)2 ways.
If we pick Type[i][0] = b, then we have (K-1) different ways to pick Type[i][1], since Type[i][0] = Type[i-1][1] = b. Hence (K-1) ways. So a total of (K-2)2 + (K-1)
Hence ANS[N] = K*(K-1) * ((K-2)2 + (K-1))(N-1)
We can use fast modular exponentiation to calculate the answer for each test case in O(log(m)),