IITK2P02 - Editorial

Problem link

contest
practice

Difficulty

SIMPLE

Pre-requisites

small fact about palindromes

Problem

Find out the number of strings of length N having alphabet size <= M such that it does not contain any palindrome as a substring. Print the answer modulo 1000000007 (10^9 + 7).

Solution

Observation 1
If a large string is palindrome, you can remove one character from left and right, still the string will remain a palindrome. this property will always hold for any palindromic string of length >= 3.

So from this observation, you can see that we just have to make sure that there are no palindromes of length 2 and 3.

Combinatorics
So we will start from left to right and try creating valid strings of length N. We can fill first position in M ways (use any character in the alphabet set). Then for the second position,
you can not use the previous character, so there are M - 1 choices. For third position, you can not use both first and second position characters, so there are M - 2 choices.
For any position >= 3, you can see that there will be M - 2 choices.

Final formula

  • If N = 1, then M
  • If N = 2, then M * (M - 1).
  • If N >= 3, then M * (M - 1) * (M - 2) (N - 2).

Calculating a^b % mod
You can use binary exponentiation idea to solve it in O(log N).

Time Complexity
O(log(N)) in computing modular exponentiation.

Tester’s solution: Will be added Later

For third position, you can not use both first and second position characters, so there are M - 3 choices. For any position >= 3, you can see that there will be M - 3 choices.

It should be M-2 choices

ty, corrected :slight_smile: