Avoid K Palindrome 2

题目描述

给定一个长度为 $N$ 的字符串 $S$，它仅由小写英文字母组成。 求通过对 $S$ 的字符进行排列（包括原字符串 $S$ 本身）所得到的字符串中，不包含长度为 $K$ 的回文串作为子串的字符串的数量。 这里，长度为 $N$ 的字符串 $T$ 被称为“包含长度为 $K$ 的回文串作为子串”，当且仅当存在一个不大于 $(N-K)$ 的非负整数 $i$，使得对于所有满足 $1 \leq j \leq K$ 的整数 $j$ 都有 $T_{i+j} = T_{i+K+1-j}$。
这里，$T_k$ 表示字符串 $T$ 的第 $k$ 个字符。

输入格式

输入从标准输入按以下格式给出： $N$ $K$ $S$

输出格式

输出通过对 $S$ 的字符排列得到的、不包含长度为 $K$ 的回文串作为子串的字符串的数量。

3 2
aab

1

5 3
zzyyx

16

10 5
abcwxyzyxw

440640

提示

$2 \leq K \leq N \leq 10$ $N$ 和 $K$ 为整数。 $S$ 是长度为 $N$ 的仅由小写英文字母组成的字符串。通过排列得到的字符串 aab 为 $aab$、$aba$ 和 $baa$。在这些字符串中，$aab$ 和 $baa$ 包含长度为 $2$ 的回文串 $aa$ 作为子串。
因此，唯一满足条件的字符串是 $aba$，所以输出 $1$。
通过排列得到的字符串 zzyyx 有 $30$ 个，其中 $16$ 个不包含长度为 $3$ 的回文串。因此，输出 $16$。

标签: AtCoder|abc363C

来源

AtCoder|abc363C