避免长度为 K 的回文

题目描述

给定一个长度为 $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

将 aab 重新排列得到的字符串有 aab、aba、baa。其中,aab 和 baa 包含长度为 $2$ 的回文 aa 作为子串。

因此,满足条件的字符串只有 aba,所以输出 $1$。

5 3
zzyyx

16

将 zzyyx 重新排列可以得到 $30$ 个字符串,其中 $16$ 个不包含长度为 $3$ 的回文。因此输出 $16$。

10 5
abcwxyzyxw

440640

数据范围

• $2 \leq K \leq N \leq 10$
• $N$ 和 $K$ 是整数。
• $S$ 是长度为 $N$、仅由小写英文字母组成的字符串。