# Hackerrank Solution: Anti-Palindromic Strings

Original Problem

You are given two integers, $$N$$ and $$M$$. Count the number of strings of length $$N$$ (under the alphabet set of size $$M$$) that doesn't contain any palindromic string of the length greater than $$1$$ as a consecutive substring.

## Input Format

Several test cases will be given to you in a single file. The first line of the input will contain a single integer, $$T$$, the number of test cases.

Then there will be $$T$$ lines, each containing two space-separated integers, $$N$$ and $$M$$, denoting a single test case. The meanings of $$N$$ and $$M$$ are described in the Problem Statement above.

## Output Format

For each test case, output a single integer - the answer to the corresponding test case. This number can be huge, so output it modulo $$10^9+7$$

## Constraints

• $$1\leq T\leq 10^5$$
• $$1\leq N,M\leq 10^9$$

## Sample Input

2
2 2
2 3

## Sample Output

2
6

## Solution

Lets analyse the problem inductive.

### Case $$N=1$$:

Since no palindromes of length $$>1$$ are allowed, all possible characters can be used, resulting in $$M$$ combinations:

$\Gamma(M, N):= M$

### Case $$N=2$$:

Since palindromes can be formed only as $$AA$$, $$BB$$, $$CC$$ and so on, the second character must be different from the first, which reduces the number of possible characters for the second place by one:

$\Gamma(M, N):= M\cdot(M - 1)$

### Case $$N=3$$:

Since we can choose any character for the third place except the two before, the number of possibilities is reduced by one again:

$\Gamma(M, N):= M\cdot(M - 1)\cdot(M - 2)$

Lets take the example with $$M=3$$: AAA, AAB, AAC, ABA, ABB, ACA, ACC, BAA, BAB, BBA, BBB, BBC, BBB, BCB, CAA, CAC, CBB, CBC, CCA, CCB and CCC have all a palindromic pattern, while ABC, ACB, BAC, BCA, CAB and CBA are anipaledrome. Which demonstrates the reasoning behind the derived formula.

### Case $$N>3$$:

Since we are looking for strings that do not contain any palindromic consecutive substrings, it is sufficient to exclude two and three-digit palindromes, since all longer palindromes contain them anyway. That is

$\Gamma(M, N):= M\cdot(M - 1)\cdot(M - 2)^{N - 2}$

Plugging cases $$N\in\{1, 2, 3\}$$ into the general formula for the last case reveals

• $$N=1: M\cdot(M - 1)\cdot(M - 2)^{1 - 2}\neq M$$
• $$N=2: M\cdot(M - 1)\cdot(M - 2)^{2 - 2} = M\cdot(M - 1)$$
• $$N=3: M\cdot(M - 1)\cdot(M - 2)^{3 - 2} = M\cdot(M - 1)\cdot(M - 2)$$

This is interesting! This suggests that Case $$N>3$$ really is $$N>1$$! Using Python with its modular exponentiation capabilities of the pow function makes it easy to implement:

def solve(n, m):

q = 1000000007

if n == 1:
return m % q

return (m * (m - 1) * pow(m - 2, n - 2, q)) % q

« Back to problem overview