← 返回题目列表

AtCoder · abc363_c

E. 避免 K 回文 2

中文机器翻译题面 查看原题

分数: 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