103632: [Atcoder]ABC363 C - Avoid K Palindrome 2
Description
Score : $300$ points
Problem Statement
You are given a string $S$ of length $N$ consisting only of lowercase English letters.
Find the number of strings obtained by permuting the characters of $S$ (including the string $S$ itself) that do not contain a palindrome of length $K$ as a substring.
Here, a string $T$ of length $N$ is said to "contain a palindrome of length $K$ as a substring" if and only if there exists a non-negative integer $i$ not greater than $(N-K)$ such that $T_{i+j} = T_{i+K+1-j}$ for every integer $j$ with $1 \leq j \leq K$.
Here, $T_k$ denotes the $k$-th character of the string $T$.
Constraints
- $2 \leq K \leq N \leq 10$
- $N$ and $K$ are integers.
- $S$ is a string of length $N$ consisting only of lowercase English letters.
Input
The input is given from Standard Input in the following format:
$N$ $K$ $S$
Output
Print the number of strings obtained by permuting $S$ that do not contain a palindrome of length $K$ as a substring.
Sample Input 1
3 2 aab
Sample Output 1
1
The strings obtained by permuting aab
are aab
, aba
, and baa
. Among these, aab
and baa
contain the palindrome aa
of length $2$ as a substring.
Thus, the only string that satisfies the condition is aba
, so print $1$.
Sample Input 2
5 3 zzyyx
Sample Output 2
16
There are $30$ strings obtained by permuting zzyyx
, $16$ of which do not contain a palindrome of length $3$. Thus, print $16$.
Sample Input 3
10 5 abcwxyzyxw
Sample Output 3
440640
Output
得分:300分
问题陈述
给定一个由小写英文字母组成的长度为N的字符串S。
找出通过排列S的字符(包括字符串S本身)得到的字符串的数量,这些字符串不包含长度为K的回文作为子字符串。
这里,如果存在一个非负整数i,不大于(N-K),使得对于每个整数j(1≤j≤K),都有T_{i+j} = T_{i+K+1-j},那么长度为N的字符串T“包含长度为K的回文作为子字符串”。
这里,T_k表示字符串T的第k个字符。
约束条件
- 2≤K≤N≤10
- N和K是整数。
- S是由小写英文字母组成的长度为N的字符串。
输入
输入从标准输入以下格式给出:
N K S
输出
打印通过排列S得到的字符串的数量,这些字符串不包含长度为K的回文作为子字符串。
示例输入1
3 2 aab
示例输出1
1
通过排列aab得到的字符串有aab、aba和baa。在这些字符串中,aab和baa包含长度为2的回文aa作为子字符串。
因此,满足条件的唯一字符串是aba,所以打印1。
示例输入2
5 3 zzyyx
示例输出2
16
通过排列zzyyx得到的字符串有30个,其中16个不包含长度为3的回文。因此,打印16。
示例输入3
10 5 abcwxyzyxw
示例输出3
440640