PROBLEM LINK:
Setter: Bogdan Ciobanu
Tester: Misha Chorniy
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Combinatorics, Modular Arithmetic.
PROBLEM:
Given three integers N, S and M, print the number of valid strings of length N using an alphabet set of size S. A valid string is a string whose suffices of size greater than 1 are not a palindrome. Print this answer modulo M.
QUICK EXPLANATION
- Build the number of non-palindrome strings of length N from small to large.
- If the number of non-palindrome strings of length i is given by cnt[i], then cnt[i] = cnt[i-1]*S-cnt[\lceil i/2 \rceil]. Just calculate this for all 1 \leq x \leq N modulo M.
EXPLANATION
Let us reverse the strings. It is easy to see that answer remains the same. Now, we have to compute the number of strings for which none of the prefixes of length greater than 1 is a palindrome.
Considering strings of length 1, we have a total of S different strings.
Considering strings of length 2, we can have S*S different strings, out of which there are S strings having a prefix of length 2, which is a palindrome. So, we have S*S-S valid strings.
Things become interesting now. See, For all these strings, suppose we append one more character, we get S*(S*S-S) different strings of length 3. Let us try to find out how many from these are valid.
See, all these string of length 3 have a non-palindrome prefix up to length 2. So, the only way any string from these shall be non-valid is when the string is a palindrome of length 3. The number of palindrome strings of length x we can have in the set is same as the number of non-palindrome strings of length \lceil x/2 \rceil which is S*S-S for x = 3 So, Number of valid strings of length 3 is S*(S*S-S) - (S*S-S).
Assuming we know the number of valid strings of length x-1 and length \lceil x/2 \rceil we can find the number of valid strings of length x. This gives us a linear time solution, to sequentially compute valid strings of length x denoted by cnt[x] using recurrence cnt[x] = cnt[x-1]*S-cnt[\lceil x/2 \rceil]. All computations to be done modulo M.
A common mistake is to subtract S^{\lceil x/2 \rceil} when asked to count the number of palindrome strings of length x. But here, the strings in the set have the property that none of the string is having any prefix being a palindrome. So, It makes sense to count only those strings whose any other prefix is not a palindrome, which is the same as cnt[\lceil x/2 \rceil].
For the people on lookout of a different solution, there also exist another solution using some inclusion-exculsion with backtracking which works for N \leq 50 only. You may find it for practice if you wish to. 
Time Complexity
Time complexity is O(N) per test case.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Tester’s solution
Editorialist’s solution
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 