C - String Coloring

Contest Duration: 2018-07-14(Sat) 12:00 - 2018-07-14(Sat) 14:30 (local time) (150 minutes) Back to Home

C - String Coloring Editorial

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : $600$ 点

問題文

長さ $2N$ の，英小文字のみからなる文字列 $S$ が与えられます。

$S$ の各文字を赤色か青色かに塗り分ける方法は $2^{2N}$ 通りありますが，このうち以下の条件を満たす塗り分け方は何通りですか？

赤色に塗られた文字を左から右に読んだ文字列と，青色に塗られた文字を右から左に読んだ文字列が一致する

制約

$1 \leq N \leq 18$
$S$ の長さは $2N$ である
$S$ は英小文字のみからなる

入力

入力は以下の形式で標準入力から与えられる。

 $N$ 
 $S$

出力

条件を満たす塗り分け方の個数を出力せよ。

入力例 1Copy

Copy

4
cabaacba

出力例 1Copy

Copy

以下の $4$ 通りの塗り分け方が存在します。

cabaacba
cabaacba
cabaacba
cabaacba

入力例 2Copy

Copy

11
mippiisssisssiipsspiim

出力例 2Copy

Copy

入力例 3Copy

Copy

4
abcdefgh

出力例 3Copy

Copy

入力例 4Copy

Copy

18
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

出力例 4Copy

Copy

9075135300

答えは32bit整数型で表せないこともあります。

Score : $600$ points

Problem Statement

You are given a string $S$ of length $2N$ consisting of lowercase English letters.

There are $2^{2N}$ ways to color each character in $S$ red or blue. Among these ways, how many satisfy the following condition?

The string obtained by reading the characters painted red from left to right is equal to the string obtained by reading the characters painted blue from right to left.

Constraints

$1 \leq N \leq 18$
The length of $S$ is $2N$ .
$S$ consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

 $N$ 
 $S$

Output

Print the number of ways to paint the string that satisfy the condition.

Sample Input 1Copy

Copy

4
cabaacba

Sample Output 1Copy

Copy

There are four ways to paint the string, as follows:

cabaacba
cabaacba
cabaacba
cabaacba

Sample Input 2Copy

Copy

11
mippiisssisssiipsspiim

Sample Output 2Copy

Copy

Sample Input 3Copy

Copy

4
abcdefgh

Sample Output 3Copy

Copy

Sample Input 4Copy

Copy

18
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Sample Output 4Copy

Copy

9075135300

The answer may not be representable as a $32$ -bit integer.