AT_agc026_c [AGC026C] String Coloring
题目描述
给定一个长度为 $2N$ 的仅由小写英文字母组成的字符串 $S$。
将 $S$ 的每个字符涂成红色或蓝色的方法共有 $2^{2N}$ 种。请问，其中有多少种涂色方案满足以下条件：
- 从左到右读取被涂成红色的字符所组成的字符串，与从右到左读取被涂成蓝色的字符所组成的字符串相同。
输入格式
输入从标准输入中给出，格式如下：
> $N$ $S$
输出格式
输出满足条件的涂色方案数。
说明/提示
## 限制条件
- $1 \leq N \leq 18$
- $S$ 的长度为 $2N$
- $S$ 仅包含小写英文字母
## 样例解释 1
存在如下 $4$ 种涂色方案：
## 样例解释 4
答案可能无法用 32 位整数类型表示。
由 ChatGPT 4.1 翻译