KAN15RTJ - Editorial

PROBLEM LINK:

Practice
Contest

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)),

x^p \equiv x^{p\bmod{\phi(m)}}\pmod{m}, m = 1000000007
\phi(m)= m-1, if m\: is \; prime
//