分数: 300 点
问题陈述
给你一个字符串 S 长度 N 仅由小写英文字母组成。
求通过排列字符得到的字符串的数量 S (包括字符串 S 本身) 不包含 长度的回文 K 作为子字符串。
这里是一个字符串 T 长度 N 据说“包含一个长度为 K 作为子字符串”当且仅当存在非负整数 i 不大于 (N-K) 这样 T_{i+j} = T_{i+K+1-j} 对于每个整数 j 与 1 \leq j \leq K.
在这里, T_k 表示 k- 字符串的第一个字符 T.
约束
- 2 \leq K \leq N \leq 10
- N 和 K 是整数。
- S 是一个长度为 N 仅由小写英文字母组成。
输入
输入由标准输入按以下格式给出:
N K S
输出
打印排列得到的字符串数量 S 不包含长度的回文数 K 作为子字符串。
示例输入 1
3 2 aab
示例输出 1
1
排列得到的字符串 aab 是 aab, aba,和 baa。其中, aab 和 baa 包含回文 aa 长度 2 作为子字符串。
因此,唯一满足条件的字符串是 aba,所以打印 1.
示例输入 2
5 3 zzyyx
示例输出 2
16
有 30 排列得到的字符串 zzyyx, 16 其中不包含长度的回文数 3。因此,打印 16.
示例输入 3
10 5 abcwxyzyxw
示例输出 3
440640