Problem link
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
