### techgig0's blog

By techgig0, 14 months ago, A special palindrome is a palindrome of size $n$ which contains at most $k$ distinct characters such that any prefix of size between $2$ and $n-1$ is not a palindrome.

You need to count the number of special palindromes.

For example, abba is a special palindrome with n = 4 and k = 2 and ababa is not a special palindrome because aba is a palindrome and its a prefix of ababa.

If n = 3 and k = 3, possible special palindromes are aba, aca, bab, bcb, cac and cbc. So the answer will be 6.

Input format

A single line comprising two integers and

Output format

Print the answer to the modulo $10^9+9$.

Input Constraints

$1 \leq n \leq 10^5$

$1 \leq k \leq 10^5$

 Sample Input Sample Output 3 2 2 4 3 6

Source

Please help with this problem as I can't find any good tutorial over internet and the code/solution provided is different than from what I thought. I don't even understand how states are defined in this.  Comments (2)
 » I don't think it's possible to understand the solution by looking at the code, so I'll describe it.Let $dp[n]$ be the number of special palindromes of size $n$.Let's build $dp[n]$ knowing $dp, ... dp[n - 1]$ by counting the number of all palindromes and subtracting the number of ones that are not special.If palindrome is not special it has a special palindrome as its prefix (take the smallest prefix that is a palindrome).Let's prove it's length is no more than $\lceil{\frac{n}{2}}\rceil$: let $l$ be $\lfloor{\frac{n}{2}}\rfloor$, $r$ be $\lceil{\frac{n}{2}}\rceil$ and $s$ be the palindrome of length $> \lceil{\frac{n}{2}}\rceil$. Then $s[l] = s[r]$, $s[l - 1] = s[r + 1]$, $s[l - 2] = s[r + 2]$ and so on til the end of the palindrome. So basically we have a palindrome of length at least 2 in the end of $s$, but we can just mirror it and get a palindrome in the beginning, so $s$ isn't special.The number of palindromes of length $n$ with fixed special palindrome of length $i$ is $k^{\lceil{\frac{n}{2}}\rceil - i}$.And the final formula for $dp[n]$ is $k^{\lceil{\frac{n}{2}}\rceil} - \sum_{i=1}^{\lceil{\frac{n}{2}}\rceil} dp[i] \cdot k^{\lceil{\frac{n}{2}}\rceil - i}$.As an exercise you can write the sum for odd and even $n$ and understand how it is changed between $n - 1$ and $n$.
 »