Basic math, Sweg
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.
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.
Worst case time complexity for each test case will be O(log N) (when M = 1 ).
Author’s solution can be found here