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 |
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.
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[1], ... 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$$$.
AC code
https://codeforces.net/blog/entry/69941?#comment-545737