使用K个字母查找大小为N的回文总数

Question

使用K个字母查找长度为N的回文总数，以使长度为2到N-1的任何前缀都不是回文。

已尝试K*((K-1)^(Math.ceil((N-2)/2)))第一位可以容纳K个字母。第二个K-1，除了第一个。第三名也是如此。由于我们需要用字母填充的一半位置的其余部分将遵循相同的条件以使其成为回文。但是它不是正确的解决方案。

Answer 1

表示M = \ceil{N / 2}。该公式取决于一个简单的观察结果，即如果长度为N的回文所具有的平凡前缀（即长度至少为2），其回文前缀的长度小于N，则它具有一个不平凡的回文前缀的长度为M最f(n)。

如果用n表示长度为2的good回文数（没有回文前缀长度为n - 1和f(N)之间的回文数），我们可以通过减去回文数的总数构成了回文数的总数，即K^M。通过以上观察，每个不良回文具有在L和2之间（包括端点）的长度M的非平凡回文前缀，这必须是一个良好的回文。每个f(L)都有L这样的前缀，并且它们中的任何一个都可以以N的方式扩展为长度为K^{M - L}的回文，所以

f(2) = K
f(N) = K^M - \sum_{L=2}^{M} K^{M - L}f(L)