← 返回题目列表

AtCoder · agc026_c

C. 字符串着色

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

给你一个字符串 S 长度 2N 由小写英文字母组成。

有 2^{2N} 为每个字符着色的方法 S 红色或蓝色。在这些方式中,有多少种满足以下条件?

  • 读取涂成红色的字符得到的字符串 从左到右 等于读取蓝色字符得到的字符串 从右到左.

约束

  • 1 \leq N \leq 18
  • 的长度 S is 2N.
  • S 由小写英文字母组成。

输入

输入由标准输入按以下格式给出:

N
S

输出

打印满足条件的字符串绘制方式的数量。


示例输入 1

4
cabaacba

示例输出 1

4

绘制字符串有四种方法,如下:

  • cabaacba
  • cabaacba
  • cabaacba
  • cabaacba

示例输入 2

11
mippiisssisssiipsspiim

示例输出 2

504

示例输入 3

4
abcdefgh

示例输出 3

0

示例输入 4

18
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

示例输出 4

9075135300

答案可能无法表示为 32位整数。