AT_abc227_e [ABC227E] Swap

题目描述

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

你最多可以进行 $K$ 次操作，每次操作可以交换 $S$ 中相邻的两个字符。请问最多可以得到多少种不同的字符串？

输入格式

输入通过标准输入按以下格式给出。

$S$ $K$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

KEY
1

输出 #1

3

输入输出样例 #2

输入 #2

KKEE
2

输出 #2

4

输入输出样例 #3

输入 #3

KKEEYY
1000000000

输出 #3

90

说明/提示

限制条件

• $2 \leq |S| \leq 30$
• $0 \leq K \leq 10^9$
• $S$ 只包含 K、E、Y

样例解释 1

对于 KEY，在最多 $1$ 次操作下可以得到的字符串有 KEY、EKY、KYE，共 $3$ 种。

样例解释 2

对于 KKEE，在最多 $2$ 次操作下可以得到的字符串有 KKEE、KEKE、EKKE、KEEK，共 $4$ 种。

由 ChatGPT 4.1 翻译