CF1634A Reverse and Concatenate

真正的愚蠢每次都能击败人工智能。 ——Terry Pratchett，《Hogfather》，《碟形世界》 给定一个长度为 $n$ 的字符串 $s$ 和一个整数 $k$。我们用 $rev(s)$ 表示字符串 $s$ 的反转（即 $rev(s) = s_n s_{n-1} \ldots s_1$）。你可以对字符串进行以下两种操作之一： - 用 $s + rev(s)$ 替换字符串 $s$； - 用 $rev(s) + s$ 替换字符串 $s$。 在原始字符串 $s$ 上恰好执行 $k$ 次操作（每次操作可以任选其中一种），最终能得到多少个不同的字符串？ 在本题中，我们用 $s + t$ 表示字符串 $s$ 和 $t$ 的连接。换句话说，$s + t = s_1 s_2 \ldots s_n t_1 t_2 \ldots t_m$，其中 $n$ 和 $m$ 分别是字符串 $s$ 和 $t$ 的长度。

第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。接下来的 $2 \cdot t$ 行包含 $t$ 个测试用例： 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 100$，$0 \le k \le 1000$），分别表示字符串的长度和操作次数。 每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，仅由小写拉丁字母组成。

对于每个测试用例，输出一个整数，表示经过恰好 $k$ 次操作后，能够得到的不同字符串的数量。每个答案占一行。 可以证明，在给定的约束下，答案不会超过 $10^9$。

在示例的第一个测试用例中： 第一次操作后，字符串 $s$ 可以变为 aabbaa 或 baaaab。第二次操作后，$s$ 有两种可能：aabbaaaabbaa 和 baaaabbaaaab。 由 ChatGPT 4.1 翻译