Problem:


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 1

4
cabaacba

Sample Output 1

4

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

cabaacba

cabaacba

cabaacba

cabaacba

Sample Input 2

11
mippiisssisssiipsspiim

Sample Output 2

504

Sample Input 3

4
abcdefgh

Sample Output 3

0

Sample Input 4

18
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Sample Output 4

9075135300

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



Sample input:
4
cabaacba


Sample output:
4

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N = int(input())
S = input()

S1 = S[:N]
S2 = S[N:][::-1]
D = defaultdict(int)
ans = 0

for i in range(2**N):
    bit = bin(2**N+i)[3:]
    red1 = "".join([d for d, s in zip(S1, bit) if s == "1"])
    blue1 = "".join([d for d, s in zip(S1, bit) if s == "0"])
    D[(red1, blue1)] += 1

for i in range(2 ** N):
    bit = bin(2 ** N + i)[3:]
    red2 = "".join([d for d, s in zip(S2, bit) if s == "1"])
    blue2 = "".join([d for d, s in zip(S2, bit) if s == "0"])
    ans += D[(blue2, red2)]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N = int(input())
S = input()

S1 = S[:N]
S2 = S[N:][::-1]
D = defaultdict(int)
keys = []
ans = 0

for i in range(2**N):
    bit = bin(2**N+i)[3:]

    red1 = tuple([d for d, s in zip(S1, bit) if s == "1"])
    blue1 = tuple([d for d, s in zip(S1, bit) if s == "0"])
    D[(red1, blue1)] += 1

    red2 = tuple([d for d, s in zip(S2, bit) if s == "1"])
    blue2 = tuple([d for d, s in zip(S2, bit) if s == "0"])
    keys.append((blue2, red2))

for key in keys:
    ans += D[key]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N = int(input())
S = input()

S1 = S[:N]
S2 = S[N:][::-1]
D = defaultdict(int)
ans = 0

for i in range(2**N):
    bit = bin(2**N+i)[3:]
    red1 = tuple([d for d, s in zip(S1, bit) if s == "1"])
    blue1 = tuple([d for d, s in zip(S1, bit) if s == "0"])
    D[(red1, blue1)] += 1

for i in range(2 ** N):
    bit = bin(2 ** N + i)[3:]
    red2 = tuple([d for d, s in zip(S2, bit) if s == "1"])
    blue2 = tuple([d for d, s in zip(S2, bit) if s == "0"])
    ans += D[(blue2, red2)]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import socket
 
if socket.gethostname() in ['N551J', 'F551C']:
    sys.stdin = open('c1.in')
 
 
def read_int_list():
    return list(map(int, input().split()))
 
 
def read_int():
    return int(input())
 
 
def read_str_list():
    return input().split()
 
 
def read_str():
    return input()
 
 
def solve():
    n = read_int()
    s = read_str()
 
    #cache = {}

    #1文字ずつredとblueに振り分けながら再帰的に関数読み出しを繰り返し、条件を満たしながらredとblue双方の長さが2nになったものの数を数える
    #探索数は基本的に2のn乗でスケールするが、条件に当てはまらないような塗分けは排除しながら進んでいく（再帰読み出しを行わず戻り値0を返す）
    def rec(red, blue):
        #一度探索したことのある文字列は即答する
        #if (red, blue) in cache:
        #    return cache[(red, blue)]

        nr = len(red)
        nb = len(blue)

        #redとblueのどちらかが長さnを超えていたら関数は0を返す
        if nr > n or nb > n:
            res = 0
            #cache[(red, blue)] = res
            return res
        #長さの合計がちょうど2nなら（上記と合わせると、両方の長さがnずつならば関数は1を返す）
        if nr + nb == 2 * n:
            res = 1
            #cache[(red, blue)] = res
            return res
        c = s[nr + nb]
        res = 0

        #文字列sの一番左の文字から始め、1文字ずつredの左側もしくはblueの右側に格納していく
        #nr+nbがn未満の場合無条件で再帰的関数読み出しを行う
        #nr+nbがnを超えた場合、新しく追加する文字cがこれまでのred, blueと整合性が取れている場合のみに再帰的関数読み出しを行う
        if nr + nb < n or (nr < n and c == blue[nr - n]):
            res += rec(red + c, blue)
        if nr + nb < n or (nb < n and c == red[n - 1 - nb]):
            res += rec(red, c + blue)

        
        #cache[(red, blue)] = res
        return res

    res2 = rec('', '')
    return res2
 
 
def main():
    res = solve()
    print(res)
 
 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = list(input())

import itertools
import copy

counter = 0
flag_list = [i for i in range(2*N)]
flag = itertools.combinations(flag_list, N)


for f in flag:
    red = ""
    s = copy.copy(S)
    for i in f:
        red += s[i]
        s[i] = "0"
    blue = "".join(s)[::-1].replace("0", "")
    if red == blue:
        counter += 1


print(counter)

Submission status: Time Limit Exceeded

Solution code:
import itertools
#import math
#from collections import deque

n=int(input())
s=list(input())

t=s[:n][::-1]
u=s[n:]
dic=dict()
for i in itertools.product(range(2),repeat=n):
	t_=[[] for _ in range(2)]
	u_=[[] for _ in range(2)]
	for j in range(n):
		t_[i[j]].append(t[j])
		u_[i[j]].append(u[j])
	t0=tuple(t_[0])
	t1=tuple(t_[1])
	u0=tuple(u_[0])
	u1=tuple(u_[1])
	if (t0,t1) not in dic:
		dic[(t0,t1)]=[1,0]
	else:
		dic[(t0,t1)][0]+=1
	if (u0,u1) not in dic:
		dic[(u0,u1)]=[0,1]
	else:
		dic[(u0,u1)][1]+=1

ans=0
for i in dic.keys():
	ans+=dic[i][0]*dic[i][1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

def product(a, b):
    '''aからbまでの整数の積'''
    p = 1
    for x in range(a, b + 1):
        p *= x
    return p
def choose(n, r):
    '''n個からr個を選ぶ選び方の個数'''
    return product(r + 1, n) // product(1, n - r)

class NotColorable(Exception):
    pass

class Colorer:
    RED = 0
    BLUE = 1

    '''彩色器'''
    def __init__(self, S):
        self.S = S
        self.__count_nchar()
        self.__count_chunk()
        self.color = [None] * len(S)  # 位置 -> 色
        self.nred  = {c: 0 for c in self.nchar}  # 文字 -> 赤の個数
        self.nblue = {c: 0 for c in self.nchar}  # 文字 -> 青の個数
        self.lpos = 0      # ここより左が埋まっている
        self.rpos = len(S) # ここから右が埋まっている
        self.lred  = []
        self.lblue = []
        self.rred  = []
        self.rblue = []

    def __count_nchar(self):
        '''各文字の出現回数を数える'''
        self.nchar = {}
        for c in self.S:
            if c in self.nchar:
                self.nchar[c] += 1
            else:
                self.nchar[c] = 1
        for c in self.nchar:
            if self.nchar[c] % 2 != 0:
                raise NotColorable
    def __count_chunk(self):
        '''その位置から始まる同じ文字の連続長を数える'''
        self.chunklen = [0] * len(S)
        self.chunklen[-1] = 1
        for i in range(len(S) - 2, -1, -1):
            if self.S[i] == self.S[i+1]:
                self.chunklen[i] = self.chunklen[i+1] + 1
            else:
                self.chunklen[i] = 1

    def trycoloring(self, f, t):
        '''S[f:t]を彩色し, 塗り分け方の個数を返す'''
        # 全文字を塗り終わった
        if f >= t:
            return 1
        # 残りの文字が全て同じ
        if t <= f + self.chunklen[f]:
            c = self.S[f]
            n = self.nchar[c]
            nr = (n // 2) - self.nred[c]  # 赤の残り数
            for i in range(t - f):
                coloring = self.colorRed if i < nr else self.colorBlue
                if not coloring(f + i):
                    for j in range(i - 1, -1, -1):
                        self.uncolor(f + j)
                    return 0
            # 元に戻す
            for j in range(t - f - 1, -1, -1):
                self.uncolor(f + j)
            return choose(t - f, nr)

        # 左右同量ずつ埋める. pos=次に埋める位置, nf,nt=次のf,t
        n = len(self.S)
        pos, nf, nt = (f, f+1, t) if f < n - t else (t-1, f, t-1)

        if self.color[pos] != None:
            return self.trycoloring(nf, nt)
        count = 0
        if self.colorRed(pos):
            count += self.trycoloring(nf, nt)
            self.uncolor(pos)
        if self.colorBlue(pos):
            count += self.trycoloring(nf, nt)
            self.uncolor(pos)
        return count

    def colorRed(self, i):
        '''S[i]を赤に塗る. 塗ることができたかどうかを返す'''
        return self.__color(i, Colorer.RED)
    def colorBlue(self, i):
        '''S[i]を青に塗る. 塗ることができたかどうかを返す'''
        return self.__color(i, Colorer.BLUE)
    def __color(self, i, col):
        '''S[i]をcolに塗る. 塗ることができたかどうかを返す'''
        if self.color[i] != None:
            self.uncolor(i)
        c = self.S[i]
        ncol = self.nred if col == Colorer.RED else self.nblue
        if ncol[c] + 1 > self.nchar[c] // 2:
            return False
        if i == self.lpos:
            if not self.__append(c, col, 0): return False
            self.lpos += 1
        elif i+1 == self.rpos:
            if not self.__append(c, col, 1): return False
            self.rpos -= 1
        self.color[i] = col
        ncol[c] += 1
        return True

    def __toappend(self, col, lr):
        rlr, blr = (self.lred, self.rred), (self.lblue, self.rblue)
        als = (rlr if col == Colorer.RED else blr)[lr]
        fls = (blr if col == Colorer.RED else rlr)[1-lr]
        return als, fls
    def __append(self, c, col, lr):
        als, fls = self.__toappend(col, lr)
        if len(als) < len(fls) and c != fls[len(als)]:
            return False
        als += c
        return True

    def uncolor(self, i):
        '''S[i]の色を消す'''
        if self.color[i] == None: return
        c = self.S[i]
        ncol = self.nred if self.color[i] == Colorer.RED else self.nblue
        if i+1 == self.lpos:
            als, _ = self.__toappend(self.color[i], 0)
            als.pop()
            self.lpos -= 1
        elif i == self.rpos:
            als, _ = self.__toappend(self.color[i], 1)
            als.pop()
            self.rpos += 1
        ncol[c] -= 1
        self.color[i] = None

def solve(S):
    '''文字列Sの各文字を2色で塗り分ける塗り分け方の個数を返す.
       ただし，赤色の字を左から右に読んだ文字列と，青色の字を
       右から左に読んだ文字列が一致.'''
    n = len(S)
    try:
        colorer = Colorer(S)
    except NotColorable:
        return 0
    count = 0
    colorer.colorRed(0)  # 一般性を失うことなく先頭文字を赤にする

    for t in range(n - 1, n // 2 - 1, -1):
        # tの右を赤にする
        if t < n - 1:
            if not colorer.colorRed(t + 1): break
        if S[0] != S[t]: continue
        # tを青の系列の右端にする
        if not colorer.colorBlue(t): continue
        # S[1:t]の彩色を試す
        count += colorer.trycoloring(1, t)
        # tを元に戻す
        colorer.uncolor(t)

    # 赤青を入れ替えた分を合わせて2倍
    return 2 * count

N = int(input())
S = input()
assert len(S) == 2 * N
print(solve(S))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()

hash = {}
for bit in range(1 << n):
    red, blue = "", ""
    for i in range(n):
        if (bit & (1 << i)) > 0:
            red += s[i]
        else:
            blue += s[i]
    hash[(red, blue)] = hash.get((red, blue), 0)+1

t = s[n:][::-1]
cnt = 0
for bit in range(1 << n):
    red, blue = "", ""
    for i in range(n):
        if (bit & (1 << i)) > 0:
            red += t[i]
        else:
            blue += t[i]
    cnt += hash.get((blue, red), 0)

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()

S1,S2 = S[:N],S[N:][::-1]

dic = {}
Ans = 0

for i in range(2**N):
    red,blue = "",""
    bits = bin(2**N+i)[3:]
    for j in range(N):
        if bits[j]=="0":
            red += S1[j]
        else:
            blue += S1[j]
    key = red+"-"+blue[::-1]
    if key not in dic.keys():
        dic[key] = 1
    else:
        dic[key] += 1

for i in range(2**N):
    red,blue = "",""
    bits = bin(2**N+i)[3:]
    for j in range(N):
        if bits[j]=="1":
            red += S2[j]
        else:
            blue += S2[j]
    key = red+"-"+blue[::-1]
    if key in dic.keys():
        Ans += dic[key]
        
print(Ans)

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8

import itertools
from collections import defaultdict


def main():
	n = int(input())
	s = input()

	left = s[:n]
	right = s[n:]
	right = right[::-1]

	ans = 0
	#print(left, right)
	for n_r in range(n+1):
		d_left = defaultdict(lambda: 0)
		d_right = defaultdict(lambda: 0)
		#print([1 if x >= n_r else 0 for x in range(n)])
		pts = itertools.combinations(list(range(n)), r = n_r)
		
		for pt in pts:
			#print(pt)
			b_l = "".join([left[i] for i in range(n) if i in pt])
			r_l = "".join([left[i] for i in range(n) if i not in pt])

			d_left[(b_l, r_l)] += 1

			b_r = "".join([right[i] for i in range(n) if i in pt])
			r_r = "".join([right[i] for i in range(n) if i not in pt])

			d_right[(b_r, r_r)] += 1

		for key in d_left:
#			print(n_r, key, d_left[key], d_right[key])
			ans += d_left[key] * d_right[key]

	print(ans)

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()

S1,S2 = S[:N],S[N:][::-1]

from itertools import product
B = list(product([0,1], repeat=N))

D1 = {}
Ans = 0

for bb in B:
    red,blue = "",""
    cnt = 0
    for i,b in enumerate(bb):
        if b == 0:
            red += S1[i]
            cnt += 1
        else:
            blue += S1[i]
    key = (cnt,red+blue[::-1])
    if key not in D1.keys():
        D1[key] = 1
    else:
        D1[key] += 1

for bb in B:
    red,blue = "",""
    cnt = 0
    for i,b in enumerate(bb):
        if b == 1:
            red += S2[i]
            cnt += 1
        else:
            blue += S2[i]
    key = (cnt,red+blue[::-1])
    if key in D1.keys():
        Ans += D1[key]

print(Ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
#import math
#from collections import deque

n=int(input())
s=list(input())

dic=dict()
for i in itertools.product(range(2),repeat=n):
	t=s[:n][::-1]
	u=s[n:]
	t_=[[] for _ in range(2)]
	u_=[[] for _ in range(2)]
	for j in range(n):
		k=t.pop()
		l=u.pop()
		t_[i[j]].append(k)
		u_[i[j]].append(l)
	t0=tuple(t_[0])
	t1=tuple(t_[1])
	u0=tuple(u_[0])
	u1=tuple(u_[1])
	if (t0,t1) not in dic:
		dic[(t0,t1)]=[1,0]
	else:
		dic[(t0,t1)][0]+=1
	if (u0,u1) not in dic:
		dic[(u0,u1)]=[0,1]
	else:
		dic[(u0,u1)][1]+=1

ans=0
for i in dic.keys():
	ans+=dic[i][0]*dic[i][1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
'''
参考: https://beta.atcoder.jp/contests/agc026/submissions/2849460
'''

n = int(input())
s = input()

s_left = s[:n]
s_right = s[n:]
m = dict()

for i in range(1 << n):
    s_red, s_blue = '', ''
    for j in range(n):
        if i & (1 << j):
            s_red = s_red  + s_left[j]
        else:
            s_blue = s_left[j] + s_blue
    tpl = (s_red, s_blue)
    if tpl in m:
        m[tpl] += 1
    else:
        m[tpl] = 1

ans = 0
for i in range(1 << n):
    s_red, s_blue = '', ''
    for j in range(n):
        if i & (1 << j):
            s_red = s_right[j] + s_red
        else:
            s_blue = s_blue + s_right[j]
        tpl = (s_red, s_blue)
    if tpl in m:
        ans += m[tpl]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
'''
参考: https://beta.atcoder.jp/contests/agc026/submissions/2849460
'''

n = int(input())
s = input()

s_left = s[:n]
s_right = s[n:]
m = dict()

for i in range(1 << n):
    s_red = s_blue = ''
    for j in range(n):
        if i & (1 << j):
            s_red = s_red  + s_left[j]
        else:
            s_blue = s_left[j] + s_blue
    if (s_red, s_blue) in m:
        m[(s_red, s_blue)] += 1
    else:
        m[(s_red, s_blue)] = 1

ans = 0
for i in range(1 << n):
    s_red = s_blue = ''
    for j in range(n):
        if i & (1 << j):
            s_red = s_right[j] + s_red
        else:
            s_blue = s_blue + s_right[j]
   
    if (s_red, s_blue) in m:
        ans += m[(s_red, s_blue)]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
'''
参考: https://beta.atcoder.jp/contests/agc026/submissions/2849460
'''

n = int(input())
s = input()

s_left = s[:n]
s_right = s[n:]
m = dict()

for i in range(1 << n):
    s_red, s_blue = '', ''
    for j in range(n):
        if i & (1 << j):
            s_red = s_red  + s_left[j]
        else:
            s_blue = s_left[j] + s_blue
    if (s_red, s_blue) in m:
        m[(s_red, s_blue)] += 1
    else:
        m[(s_red, s_blue)] = 1

ans = 0
for i in range(1 << n):
    s_red, s_blue = '', ''
    for j in range(n):
        if i & (1 << j):
            s_red = s_right[j] + s_red
        else:
            s_blue = s_blue + s_right[j]
   
    if (s_red, s_blue) in m:
        ans += m[(s_red, s_blue)]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
'''
参考: https://beta.atcoder.jp/contests/agc026/submissions/2849460
'''

if __name__ == '__main__':
    n = int(input())
    s = input()

    s_left = s[:n]
    s_right = s[n:]
    m = dict()

    '''
    1 << n　は　2 ** n
    '''
    
    for i in range(2 ** n):
        s_red, s_blue = '', ''
        for j in range(n):
            if i & (2 ** j):
                s_red = s_red  + s_left[j]
            else:
                s_blue = s_left[j] + s_blue
        if (s_red, s_blue) in m:
            m[(s_red, s_blue)] += 1
        else:
            m[(s_red, s_blue)] = 1

    ans = 0
    for i in range(2 ** n):
        s_red, s_blue = '', ''
        for j in range(n):
            if i & (2 ** j):
                s_red = s_right[j] + s_red
            else:
                s_blue = s_blue + s_right[j]
       
        if (s_red, s_blue) in m:
            ans += m[(s_red, s_blue)]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
'''
参考: https://beta.atcoder.jp/contests/agc026/submissions/2849460
'''

if __name__ == '__main__':
    n = int(input())
    s = input()

    s_left = s[:n]
    s_right = s[n:]
    m = dict()

    '''
    1 << n　は　2 ** n
    '''
    
    for i in range(2 ** n):
        s_red, s_blue = '', ''
        for j in range(n):
            if i & (2 ** j):
                s_red += s_left[j]
            else:
                s_blue += s_left[j]
        if (s_red, s_blue) in m:
            m[(s_red, s_blue)] += 1
        else:
            m[(s_red, s_blue)] = 1

    ans = 0
    for i in range(2 ** n):
        s_red, s_blue = '', ''
        for j in range(n):
            if i & (2 ** j):
                s_red += s_right[j]
            else:
                s_blue += s_right[j]

        s_red = s_red[::-1]
        s_blue = s_blue[::-1]
        
        if (s_red, s_blue) in m:
            ans += m[(s_red, s_blue)]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

N = read()
S = input()

former = defaultdict(int)
latter = defaultdict(int)

def power(n):
  return chain(*(combinations(range(n), r) for r in range(n+1)))

for p in power(N):
  bs1 = []; rs1 = []; bs2 = []; rs2 = []
  for i in range(N):
    if i in p:
      rs1.append(S[i])
      rs2.append(S[-1-i])
    else:
      bs1.append(S[i])
      bs2.append(S[-1-i])
  former["".join(rs1), "".join(bs1)] += 1
  latter["".join(bs2), "".join(rs2)] += 1

ans = 0
for k, v in former.items():
  if k in latter:
    ans += v * latter[k]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
'''
参考: https://beta.atcoder.jp/contests/agc026/submissions/2849460
'''

if __name__ == '__main__':
    n = int(input())
    s = input()

    s_left = s[:n]
    s_right = s[n:]
    m = dict()

    Bs = [bin(x)[2:].zfill(n) for x in range(2 ** n)]
    intBs = [list(map(int, list(x))) for x in Bs]

    for b in intBs:
        s_red, s_blue = '', ''
        for i in range(n):
            if b[i] == 0:
                s_red += s_left[i]
            else:
                s_blue += s_left[i]
        if (s_red, s_blue) in m:
            m[(s_red, s_blue)] += 1
        else:
            m[(s_red, s_blue)] = 1

    ans = 0
    for b in intBs:
        s_red, s_blue = '', ''
        for i in range(n):
            if b[i] == 0:
                s_red += s_right[i]
            else:
                s_blue += s_right[i]

        s_red = s_red[::-1]
        s_blue = s_blue[::-1]
        
        if (s_red, s_blue) in m:
            ans += m[(s_red, s_blue)]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

N = read()
S = input()

former = defaultdict(int)
latter = defaultdict(int)

for bits in range(1 << N):
  bs1 = []; rs1 = []; bs2 = []; rs2 = []
  for i in range(N):
    if (1 << i) & bits:
      rs1.append(S[i])
      rs2.append(S[-1-i])
    else:
      bs1.append(S[i])
      bs2.append(S[-1-i])
  former["".join(rs1), "".join(bs1)] += 1
  latter["".join(bs2), "".join(rs2)] += 1

ans = 0
for k, v in former.items():
  if k in latter:
    ans += v * latter[k]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

N = read()
S = input()

former = defaultdict(int)
latter = defaultdict(int)

for bits in range(1 << N):
  bs1 = []; rs1 = []; bs2 = []; rs2 = []
  for i in range(N):
    if (1 << i) & bits:
      rs1.append(S[i])
      rs2.append(S[N+i])
    else:
      bs1.append(S[i])
      bs2.append(S[N+i])
  former["".join(rs1), "".join(bs1)] += 1
  latter["".join(reversed(bs2)), "".join(reversed(rs2))] += 1

ans = 0
for s in former.keys():
  ans += former[s] * latter[s]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

N = read()
S = input()

former = defaultdict(int)
latter = defaultdict(int)

for bits in range(2**N):
  bs = []; rs = []
  for i in range(N):
    if (1 << i) & bits:
      rs.append(S[i])
    else:
      bs.append(S[i])
  former["".join(rs), "".join(bs)] += 1

for bits in range(2**N):
  bs = []; rs = []
  for i in range(N):
    if (1 << i) & bits:
      rs.append(S[N+i])
    else:
      bs.append(S[N+i])
  latter["".join(reversed(bs)), "".join(reversed(rs))] += 1

ans = 0
for s in former.keys():
  ans += former[s] * latter[s]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

n = int(input())
s = input()

s1 = s[:n]
s2 = s[-1:-(n + 1):-1]
s_dict = collections.defaultdict(lambda: [0, 0])
for i in range(2 ** n):
    bin_i = bin(i + 2 ** n)
    sequence1 = ""
    sequence1_inverse = ""
    for j in range(n):
        if bin_i[j + 3] == "1":
            sequence1 += s1[j]
        else:
            sequence1_inverse += s1[j]
    s_dict[(sequence1, sequence1_inverse)][0] += 1
for i in range(2 ** n):
    bin_i = bin(i + 2 ** n)
    sequence2 = ""
    sequence2_inverse = ""
    for j in range(n):
        if bin_i[j + 3] == "1":
            sequence2 += s2[j]
        else:
            sequence2_inverse += s2[j]
    s_dict[(sequence2, sequence2_inverse)][1] += 1
ans = 0
s_dict =dict(s_dict)
while s_dict:
    s_tuple = s_dict.popitem()
    ans += s_tuple[1][0] * s_tuple[1][1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

n = int(input())
s = input()

s1 = s[:n]
s2 = s[-1:-(n + 1):-1]
s_dict = collections.defaultdict(lambda: [0, 0])
for i in range(2 ** n):
    bin_i = bin(i + 2 ** n)
    sequence1 = ""
    sequence1_inverse = ""
    for j in range(n):
        if bin_i[j + 3] == "1":
            sequence1 += s1[j]
        else:
            sequence1_inverse += s1[j]
    s_dict[(sequence1, sequence1_inverse)][0] += 1
for i in range(2 ** n):
    bin_i = bin(i + 2 ** n)
    sequence2 = ""
    sequence2_inverse = ""
    for j in range(n):
        if bin_i[j + 3] == "1":
            sequence2 += s2[j]
        else:
            sequence2_inverse += s2[j]
    s_dict[(sequence2, sequence2_inverse)][1] += 1
ans = 0
for i in dict(s_dict):
    s_list = dict(s_dict)[i]
    ans += s_list[0] * s_list[1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

n = int(input())
s = input()

s1 = s[:n]
s2 = s[-1:-(n + 1):-1]
s_1 = collections.defaultdict(int)
s_2 = collections.defaultdict(int)
for i in range(2 ** n):
    bin_i = bin(i + 2 ** n)
    sequence1 = ""
    sequence1_inverse = ""
    sequence2 = ""
    sequence2_inverse = ""
    for j in range(n):
        if bin_i[j + 3] == "1":
            sequence1 += s1[j]
            sequence2 += s2[j]
        else:
            sequence1_inverse += s1[j]
            sequence2_inverse += s2[j]
    s_1[(sequence1, sequence1_inverse)] += 1     
    s_2[(sequence2, sequence2_inverse)] += 1
ans = 0
for i in dict(s_1):
    if i in dict(s_2):
        ans += dict(s_1)[i] * dict(s_2)[i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product, compress

N = int(input())
Ss = input()

Fss = [list(compress(Ss[:N], sels))[::-1] for sels in product([0, 1], repeat=N)]

ans = 0
for iFs in range(2 ** N):
    Fs = Fss[iFs]
    Gs = Fss[2 ** N - 1 - iFs]

    lenF = len(Fs)
    lenG = N - lenF
    dp = [1] + [0] * lenF
    for i, s in enumerate(Ss[N:], 1):
        dp2 = [0] * (lenF + 1)
        flg = False
        for j in range(lenF + 1):
            if 0 <= j-1 and s == Fs[j-1]:
                dp2[j] += dp[j-1]
            if 0 <= i-j-1 < lenG and s == Gs[i-j-1]:
                dp2[j] += dp[j]
            if dp2[j]:
                flg = True
        dp = dp2
        if not flg: break

    ans += dp[lenF]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

def solve(f):
    n = f.read_int()
    s = f.read_str()

    memo = {}

    ans = 0
    for mask in xrange(1<<n):
        red = ''
        blue = ''
        for i in xrange(n):
            ci = (mask>>i) & 1
            if ci:
                red += s[i]
            else:
                blue += s[i]
        r = blue[::-1]
        b = red[::-1]

        if sorted(s) != sorted(blue+red+b+r): continue
        if (r, b) in memo:
            ans += memo[(r,b)]
            continue

        dp = [[[0 for _ in xrange(len(b)+1)] for _ in xrange(len(r)+1)] for _ in xrange(n+1)]
        dp[0][0][0] = 1

        for i in xrange(n):
            si = s[n+i]
            for ri in xrange(max(0,len(r)-n+i), len(r)+1):
                for bi in xrange(max(0,len(b)-n+i),len(b)+1):
                    if ri < len(r) and r[ri] == si:
                        dp[i+1][ri+1][bi] += dp[i][ri][bi]
                    if bi < len(b) and b[bi] == si:
                        dp[i+1][ri][bi+1] += dp[i][ri][bi]

        memo[(r,b)] = dp[-1][-1][-1]
        ans += dp[-1][-1][-1]

    return ans


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
import math

n = int(input())
s = input().strip()

def split(s, mask):
    a, b = '', ''
    for i, c in enumerate(s):
        if i in mask:
            a = a + c
        else:
            b = b + c
    return a, b

def strcount(s):
    res = {}
    for c in s:
        try:
            res[c] += 1
        except KeyError:
            res[c] = 1
    return res

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def hantei(s, mask):
    a, b = split(s, mask)
    b = b[::-1]
    if a == b:
        return True
    return False

res = 0
flag = False

count = strcount(s)
if len(count) == 1:
    res = combinations_count(2 * n, n)
else:
    for c in count:
        if count[c] % 2 != 0:
            res = 0
            flag = True
            break
    if not flag:
        i = 0
        for mask in combinations(range(2 * n), n):
            if i >= combinations_count(2 * n, n) // 2:
                break
            if hantei(s, mask):
                res += 1
print(res)