PROBLEM LINK:
Authors: Sahil Grover
Testers: Vaibhav Daga
Editorialist: Sahil Grover
DIFFICULTY:
Easy
PREREQUISITES:
Basic math, Sweg
PROBLEM:
We need to find the number of strings of length N made by using at most K alphabets such that every substring of length exactly equal to M is a palindrome.
EXPLANATION:
In this problem we have to consider 5 cases:
if M > N : No substring of length M is possible in a string of length N so we simply print “Sweg”(without quotes).
if M = 1 : Any string of length N is possible so the answer is K^N.
if M = N : The string itself must be a palindrome. So the answer will be K^((N+1)/2) (’/’ implies integer division).
if 1 < M < N :
if M is odd, the answer will be K^2.
if M is even, the answer will be K.
The answer can be evaluated using Recursive Modular Exponentiation.
Time Complexity:
Worst case time complexity for each test case will be O(log N) (when M = 1 ).
AUTHOR’S SOLUTION:
Author’s solution can be found here