Score : $500$ points

问题描述

给定一个仅包含字符 K、E 和 Y 的字符串 $S$。

请问，在最多进行 $K$ 次相邻字符交换的情况下，可以得到多少种不同的字符串？

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

Given is a string $S$ consisting of K, E, Y.

How many strings are there that can be obtained with at most $K$ swaps of two adjacent characters in $S$?

Constraints

• $2 \leq |S| \leq 30$
• $0 \leq K \leq 10^9$
• $S$ consists of K, E, Y.

Input

Input is given from Standard Input in the following format:

$S$

$K$

Output

Print the answer.

Sample Input 1

KEY
1

Sample Output 1

3

With at most one swap, there are three strings that can be obtained: KEY, EKY, KYE.

Sample Input 2

KKEE
2

Sample Output 2

4

With at most two swaps, there are four strings that can be obtained: KKEE, KEKE, EKKE, KEEK.

Sample Input 3

KKEEYY
1000000000

Sample Output 3

90

update @ 2024/3/10 09:57:17