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:   c a b a a c b a  c a b a a c b a  c a b a a c b a  c a b a a c b a        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.

Solution (Python):

from collections import defaultdict

N = int(input())
S = input()
A, B = S[:N], S[N:]
D = defaultdict(int)
ans = 0

def paint(X, i):
    r = ""
    b = ""
    for j, k in enumerate(format(i, "b").zfill(N)):
        if k == "1":
            r += X[j]
        else:
            b += X[j]
    return r, b

for i in range(2**N):
    r, b = paint(A, i)
    D[(r, b)] += 1

for i in range(2**N):
    r, b = paint(B, i)
    ans += D[(b[::-1], r[::-1])]

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

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

	dic = {}
	for i in range(0,2**n):
		temp = bin(i)[2:].zfill(n)
		ts1 = ""
		ts2 = ""
		for j in range(n):
			if temp[j] == "1":
				ts1 += s[j]
			else:
				ts2 += s[j]
		if (ts1, ts2) in dic.keys():
			dic[(ts1,ts2)] += 1
		else:
			dic.update({(ts1,ts2):1})
			
	ans = 0
	s = s[::-1]
	for i in range(0,2**n):
		temp = bin(i)[2:].zfill(n)
		ts1  =""
		ts2 = ""
		for j in range(n):
			if temp[j] == "1":
				ts1 += s[j]
			else:
				ts2 += s[j]
		if (ts1, ts2) in dic.keys():
			ans += dic[(ts1,ts2)]
	print(ans)

main()

Solution (Python):


from collections import Counter
from itertools import product

def getLeft(in_string, N):
    return in_string[:N]

def getRight(in_string, N):
    return in_string[2*N-1:N-1:-1]

def getDict(left_seq):
    tmp_n = len(left_seq)
    r_dict = Counter()
    for bit in product(range(2), repeat=tmp_n):
        red_left = ""
        blue_left = ""
        for i in range(tmp_n):
            if bit[i]:
                red_left += left_seq[i]
            else:
                blue_left += left_seq[i]
        r_dict[red_left + "-" + blue_left] += 1
    return r_dict

def getMatch(left, right):
    res = 0
    for i in left.keys():
        res += left[i]*right[i]
        
    return res

if __name__ == "__main__":
    N = int(input())
    Seq = input()
    print(getMatch(getDict(getLeft(Seq, N)), getDict(getRight(Seq, N))))

Solution (Python):
from collections import defaultdict

N=int(input())
S=input()
S1=S[:N]
S2=S[N:][::-1]

bit=1<<N

firstList=[]
secondList=defaultdict(int)
for i in range(bit):
  blue=""
  red=""
  blue2=""
  red2=""
  for j in range(N):
    if (i>>j)%2:
      blue+=S1[j]
      blue2+=S2[j]
    else:
      red+=S1[j]
      red2+=S2[j]
  firstList.append(blue + "-" + red)
  secondList[blue2 + "-" + red2]+=1

ans=0
for s in firstList:
  ans+=secondList[s]
print(ans)

Solution (Python):
from collections import Counter
from itertools import product

N=int(input())
S=list(input())
S_rev=list(reversed(S[N:])) 


leftlist=[] 
rightlist=[] 

for bit in product(range(2),repeat=N):
  
  red_left='' 
  blue_left=''
  red_right=''
  blue_right=''
  for j in range(N):
    if bit[j] == 1:
      red_left+=S[j] 
      blue_right+=S_rev[j]
    else:
      blue_left+=S[j]
      red_right+=S_rev[j]
  leftlist.append("".join(red_left + "|" + blue_left)) 
  rightlist.append("".join(blue_right + "|" + red_right)) 
left=Counter(leftlist)
right=Counter(rightlist)

answer=0

for key,value in left.items():
  answer+= value * right[key] 
print(answer)

Solution (Python):
from collections import Counter
from itertools import product
N = int(input())
S = input()
Left = Counter()
Right = Counter()
S_left = S[:N]
S_right = S[2*N-1:N-1:-1]
for B in product(range(2),repeat = N):
    red_left = ''
    blue_left = ''
    red_right = ''
    blue_right = ''
    for i in range(N):
        if B[i]:
            red_left += S_left[i]
            red_right += S_right[i]
        else:
            blue_left += S_left[i]
            blue_right += S_right[i]
    Left[red_left + '|' + blue_left] += 1
    Right[blue_right + '|' + red_right] += 1
ans = 0
for i in Left.keys():
    ans += Left[i]*Right[i]
print(ans)

Solution (Python):
from collections import Counter
from itertools import product

n = int(input())
s = list(input())
s_l = list(reversed(s[n:]))

red = Counter(["".join([s[i] for i in range(n) if bit[i] == 1] + ["|"] + [s[i] for i in range(n) if bit[i] == 0]) for bit in product(range(2), repeat=n)])
blue = Counter(["".join([s_l[i] for i in range(n) if bit[i] == 1] + ["|"] + [s_l[i] for i in range(n) if bit[i] == 0]) for bit in product(range(2), repeat=n)])

ans = 0

for key, value in red.items():
	ans += value * blue[key]

print(ans)

Solution (Python):
from collections import Counter
from itertools import product

n = int(input())
s = list(input())
s_l = list(reversed(s[n:]))

red = Counter(["".join([s[i] for i in range(n) if bit[i] == 1] + ["|"] + [s[i] for i in range(n) if bit[i] == 0]) for bit in product(range(2), repeat=n)])
blue = Counter(["".join([s_l[i] for i in range(n) if bit[i] == 1] + ["|"] + [s_l[i] for i in range(n) if bit[i] == 0]) for bit in product(range(2), repeat=n)])

ans = 0

for key, value in red.items():
	ans += value * blue[key]

print(ans)

Solution (Python):
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):
    ans += s_1.get(i, 0) * s_2.get(i, 0)
    '''
    if i in dict(s_2):
        ans += dict(s_1)[i] * dict(s_2)[i]
    '''
print(ans)

Solution (Python):
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)

strlist = []

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):
    ans += s_1.get(i, 0) * s_2.get(i, 0)
    '''
    if i in dict(s_2):
        ans += dict(s_1)[i] * dict(s_2)[i]
    '''
print(ans)

Solution (Python):
from collections import defaultdict

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

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

ans = 0
D = defaultdict(int)

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)

Solution (Python):
import itertools
from collections import Counter

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

t=s[:n][::-1]
u=s[n:]
tc=Counter()
uc=Counter()
for i in itertools.product(range(2),repeat=n):
	t0=""
	t1=""
	u0=""
	u1=""
	for j in range(n):
		if not i[j]:
			t0+=t[j]
			u0+=u[j]
		else:
			t1+=t[j]
			u1+=u[j]
	tc[t0+"-"+t1]+=1
	uc[u0+"-"+u1]+=1

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

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

sleft = S[:N]
sright = S[2*N:N-1:-1]
ldict,rchoise = {},[]
count = 0
for i in range(2**N):
    red = bin(i)[2:].zfill(N)
    leftred, rightred, leftblue, rightblue = "","","",""
    for j in range(N):
        if red[j] == "1":
            leftred += sleft[j]
            rightred += sright[j]
        else:
            leftblue += sleft[j]
            rightblue += sright[j]
    if leftred + "-" + leftblue in ldict.keys():
        ldict[leftred + "-" + leftblue] += 1
    else:
        ldict[leftred + "-" + leftblue] = 1
    rchoise.append(rightred + "-" + rightblue)
    
for i in rchoise:
    count += ldict.get(i, 0)
print(count)

Solution (Python):
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)

Solution (Python):
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 = {}

    
    
    def rec(red, blue):
        
        if (red, blue) in cache:
            return cache[(red, blue)]

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

        
        if nr > n or nb > n:
            res = 0
            cache[(red, blue)] = res
            return res
        
        if nr + nb == 2 * n:
            res = 1
            cache[(red, blue)] = res
            return res
        c = s[nr + nb]
        res = 0

        
        
        
        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()

Solution (Python):
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
n=i1()
s=input()
from collections import defaultdict
ad1 = defaultdict(int)
ad2 = defaultdict(int)

for i in range(1<<n):
 a=""
 b=""
 for j in range(n):
  if i & (1<<j) ==0:
     a+=s[j]
  else:
     b+=s[j]
 ad1[a+"_"+b[::-1]]+=1
 a=""
 b=""
 for j in range(n):
  if i & (1<<j):
     a+=s[j+n]
  else:
     b+=s[j+n]
 ad2[b[::-1]+"_"+a]+=1
 
cc=0
for i in ad1.keys():
 cc+=ad1[i]*ad2[i]

print(cc)

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

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

dic = {}
keys = []
Ans = 0

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

for key in keys:
    Ans += dic.get(key, 0)

print(Ans)

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

result = 0

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

def calc(s, x):
    s1 = ""
    s2 = ""
    for c in s:
        if x & 1:
            s1 += c
        else:
            s2 += c
        x >>= 1
    return s1, s2

from collections import defaultdict

kv = defaultdict(int)

for i in range(2**N):
    kv[calc(S2, i)] += 1

for i in range(2**N):
    result += kv[calc(S1, i)]

print(result)

Solution (Python):
import itertools



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

t=s[:n][::-1]
u=s[n:]
dic=dict()
for i in itertools.product(range(2),repeat=n):
	t_=[""]*2
	u_=[""]*2
	for j in range(n):
		t_[i[j]]+=t[j]
		u_[i[j]]+=u[j]
	if (t_[0],t_[1]) not in dic:
		dic[(t_[0],t_[1])]=[1,0]
	else:
		dic[(t_[0],t_[1])][0]+=1
	if (u_[0],u_[1]) not in dic:
		dic[(u_[0],u_[1])]=[0,1]
	else:
		dic[(u_[0],u_[1])][1]+=1

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

Solution (Python):
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)

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

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

dic = {}
keys = []
Ans = 0

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

for key in keys:
    Ans += dic.get(key,0)

print(Ans)

Solution (Python):


import itertools
from collections import defaultdict


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

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

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

			d_left[(b_l, r_l)] += 1
			d_right[(b_r, r_r)] += 1

		for key in d_left:

			ans += d_left[key] * d_right[key]

	print(ans)

	

if __name__ == '__main__':
	main()

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

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

dic = {}
Ans = 0
keys = []

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

for k in keys:
    Ans += dic.get(k,0)

print(Ans)

Solution (Python):
from collections import Counter
N = int(input())
S = input()
ctr1 = Counter()
ctr2 = Counter()

for b in range(2**N):
    blue = red = ''
    for k in range(N):
        if b & (1<<k):
            blue += S[k]
        else:
            red += S[k]
    ctr1[(blue,red)] += 1

T = S[:-N-1:-1]
for b in range(2**N):
    blue = red = ''
    for k in range(N):
        if b & (1<<k):
            blue += T[k]
        else:
            red += T[k]
    ctr2[(blue,red)] += 1

ans = 0
for k,v in ctr1.items():
    ans += v * ctr2[k]
print(ans)

Solution (Python):
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(lambda: 0)
latter = defaultdict(lambda: 0)

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

def solve(N, S):
  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]

  return ans

print(solve(N, S))

Solution (Python):
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()

ans = 0

for bits in range(2**N):
  bs = []; rs = []
  for i in range(N):
    if ((1 << i) & bits) == 0:
      rs.append(S[i])
    else:
      bs.append(S[i])
  rs.reverse(); bs.reverse()

  lenr = len(rs); lenb = len(bs)
  dp = [[0] * (lenb + 1) for _ in range(lenr + 1)]
  dp[0][0] = 1
  for i in range(lenr + 1):
    for j in range(lenb + 1):
      if i < lenr and rs[i] == S[N+i+j]:
        dp[i+1][j] += dp[i][j]
      if j < lenb and bs[j] == S[N+i+j]:
        dp[i][j+1] += dp[i][j]
  ans += dp[-1][-1]

print(ans)

Solution (Python):
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)

Solution (Python):

import sys

input=sys.stdin.readline

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

memo={}
def getans(a,b,c):
    while a and c and a[0]==c[-1]:
        a=a[1:]
        c=c[:-1]
    if a and c: return 0
    if b=="":
        if a=="" and c=="": return 1
        else: return 0
    key=a+"/"+b+"/"+c
    if key in memo: return memo[key]
    
    ans=0
    for i in range(1,len(b)):
        if b[0]==b[i]:
            ans+=getans(a,b[1:i],b[i+1:]+c)
    
    ans+=getans(a+b[0],b[1:],c)
    memo[key]=ans
    
    return ans

print(getans("",s,"")*2)

Solution (Python):


import sys
import math
import itertools as it
from collections import deque

sys.setrecursionlimit(10000000)

def func():
    N = input()
    S = raw_input()

    S1 = S[:N]
    S2 = S[N:]

    m = {}

    for i in range((1 << N)):
        s1 = s2 = ''
        for j in range(N):
            if(i & (1 << j)):
                s1 = s1 + S1[j]
            else:
                s2 = S1[j] + s2
        if (s1, s2) in m:
            m[(s1, s2)] += 1
        else:
            m[(s1, s2)] = 1

    ans = 0

    for i in range((1 << N)):
        s1 = s2 = ''
        for j in range(N):
            if(i & (1 << j)):
                s1 = S2[j] + s1
            else:
                s2 = s2 + S2[j]
        if (s1, s2) in m:
            ans += m[(s1, s2)]

    print ans

func()

Solution (Python):


import sys
import math
import itertools as it
from collections import deque

sys.setrecursionlimit(10000000)

def func():
    N = input()
    S = raw_input()

    S1 = S[:N]
    S2 = S[N:]

    m = {}

    for i in range((1 << N)):
        s1 = s2 = ''
        for j in range(N):
            if(i & (1 << j)):
                s1 = s1 + S1[j]
            else:
                s2 = S1[j] + s2
        if (s1, s2) in m:
            m[(s1, s2)] += 1
        else:
            m[(s1, s2)] = 1

    ans = 0

    for i in range((1 << N)):
        s1 = s2 = ''
        for j in range(N):
            if(i & (1 << j)):
                s1 = S2[j] + s1
            else:
                s2 = s2 + S2[j]
        if (s1, s2) in m:
            ans += m[(s1, s2)]

    print ans

func()

Solution (Python):
from collections import defaultdict
from itertools import combinations


def get_pair(s, cmb):
    g, h = 0, 0
    for i in range(n):
        if i in cmb:
            g <<= 5
            g += s[i]
        else:
            h <<= 5
            h += s[i]
    return g, h


def patterns(k, d, e):
    ret = 0
    f = defaultdict(int)
    for cmb in combinations(range(n), k):
        f[get_pair(d, cmb)] += 1
    for cmb in combinations(range(n), k):
        ret += f[get_pair(e, cmb)]
    return ret


def solve(n, b):
    d = b[:n]
    e = b[2 * n - 1:n - 1:-1]
    ans = 0

    if n % 2 == 0:
        for k in range(n // 2):
            ans += 2 * patterns(k, d, e)
        ans += patterns(n // 2, d, e)
    else:
        for k in range(n // 2 + 1):
            ans += 2 * patterns(k, d, e)
    return ans


n = int(input())
s = input()
a = ord('a') - 1
b = [ord(c) - a for c in s]
print(solve(n, b))

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().strip().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def ref_slv(N, S):
    ans = 0

    for i in combinations(range(0, 2*N), N):
        l = []
        r = []
        for j in range(2*N):
            if j in i:
                l.append(S[j])
            else:
                r.append(S[j])

        if ''.join(l) == ''.join(reversed(r)):
            ans += 1

    return ans


@mt
def slv(N, S):
    ans = 0

    l = S[:N]
    r = S[N:][::-1]
    ld = defaultdict(lambda: 0)
    rd = defaultdict(lambda: 0)

    for i in range(N+1):
        for j in combinations(range(N), i):
            lb = []
            lr = []
            rb = []
            rr = []
            for k in range(N):
                if k in j:
                    lb.append(l[k])
                    rr.append(r[k])
                else:
                    lr.append(l[k])
                    rb.append(r[k])
            ld[(''.join(lr), ''.join(lb))] += 1
            rd[(''.join(rr), ''.join(rb))] += 1
    for k, v in ld.items():
        if k in rd:
            ans += v * rd[k]

    return ans


def main():
    
    
    N = read_int()
    S = read_str()
    print(slv(N, S))


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().strip().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def ref_slv(N, S):
    ans = 0

    for i in combinations(range(0, 2*N), N):
        l = []
        r = []
        for j in range(2*N):
            if j in i:
                l.append(S[j])
            else:
                r.append(S[j])

        if ''.join(l) == ''.join(reversed(r)):
            ans += 1

    return ans


@mt
def slv(N, S):
    ans = 0

    l = S[:N]
    r = S[N:][::-1]
    ld = defaultdict(lambda: 0)
    rd = defaultdict(lambda: 0)

    for i in range(N+1):
        for j in combinations(range(N), i):
            lb = []
            lr = []
            rb = []
            rr = []
            for k in range(N):
                if k in j:
                    lb.append(l[k])
                    rr.append(r[k])
                else:
                    lr.append(l[k])
                    rb.append(r[k])
            ld[(''.join(lr), ''.join(lb))] += 1
            rd[(''.join(rr), ''.join(rb))] += 1
    for k, v in ld.items():
        if k in rd:
            ans += v * rd[k]

    return ans


def main():
    
    
    N = read_int()
    S = read_str()
    print(slv(N, S))


if __name__ == '__main__':
    main()

Solution (Python):


import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq





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

    cand1 = collections.defaultdict(int)
    cand2 = collections.defaultdict(int)

    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]
        cand1[(red,blue)] += 1

        red = ''
        blue = ''
        for i in xrange(n):
            ci = (mask>>i) & 1
            if ci:
                red += s[2*n-i-1]
            else:
                blue += s[2*n-i-1]
        cand2[(red,blue)] += 1

    ans = 0
    for k, v in cand1.items():
        ans += v * cand2[k]

    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 
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Solution (Python):
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:]):
        dp2 = [0] * (lenF + 1)
        for j in range(lenF + 1):
            if dp[j] == 0: continue
            if j < lenF and s == Fs[j]:
                dp2[j+1] += dp[j]
            if 0 <= i-j < lenG and s == Gs[i-j]:
                dp2[j] += dp[j]
        dp = dp2

    ans += dp[lenF]

print(ans)

Solution (Python):
N = int(input())
S = input()
Sl = S[:N]
Sr = S[N:]

from collections import defaultdict
L = defaultdict(int)
R = defaultdict(int)
for i in range(1<<N):
    t1 = ""
    t2 = ""
    for j in range(N):
        if i & (1<<j):
            t1 += Sl[j]
    for j in range(N-1, -1, -1):
        if not i & (1<<j):
            t2 += Sl[j]
    L[(t1, t2)] += 1
    t1 = ""
    t2 = ""
    for j in range(N-1, -1, -1):
        if i & (1<<j):
            t1 += Sr[j]
    for j in range(N):
        if not i & (1<<j):
            t2 += Sr[j]
    R[(t1, t2)] += 1
ans = 0
for k, v in L.items():
    ans += R[k] * v
print(ans)

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

memo = {}
def dp(s1, s2, l1, l2, r1, r2, i):
  
  if s1 + s2 in memo:
    return memo[s1 + s2]
  if i == 2 * N:
    ret = int(s1 == s2)
  else:
    ret = 0
    if i % 2 == 0:
      c = S[i // 2]
      
      if s1[l1] == ' ' and (s2[l1] == ' ' or s2[l1] == c):
        ret += dp(s1[:l1] + c + s1[l1+1:], s2, l1+1, l2, r1, r2, i+1)
      if s2[r2] == ' ' and (s1[r2] == ' ' or s1[r2] == c):
        ret += dp(s1, s2[:r2] + c + s2[r2+1:], l1, l2, r1, r2-1, i+1)
    else:
      c = S[-(i // 2 + 1)]
      
      if s1[r1] == ' ' and (s2[r1] == ' ' or s2[r1] == c):
        ret += dp(s1[:r1] + c + s1[r1+1:], s2, l1, l2, r1-1, r2, i+1)
      if s2[l2] == ' ' and (s1[l2] == ' ' or s1[l2] == c):
        ret += dp(s1, s2[:l2] + c + s2[l2+1:], l1, l2+1, r1, r2, i+1)
  memo[s1 + s2] = ret
  return ret


a = S[0] + (' ' * (N-1))
b = ' ' * N

print(dp(a, b, 1, 0, N-1, N-1, 1) * 2)

Solution (Python):

N = int(input())
S = list(input())
S1 = S[:N]
S2 = S[2*N-1:N-1:-1]

dict_1 = dict()
q_list = [""]*(2**N)
res = 0

for i in range(2**N):
    sb = bin(2**N+i)[3:]
    red = []
    blue = []
    red2 = []
    blue2 = []
    for j in range(N):
        if sb[j]=="0":
            red.append(S1[j])
            red2.append(S2[j])
        else:
            blue.append(S1[j])
            blue2.append(S2[j])
    sss = "".join(red+["|"]+blue)
    sss2 = "".join(red2+["|"]+blue2)
    if sss not in dict_1.keys():
        dict_1[sss] = 1
    else:
        dict_1[sss] += 1
    q_list[i] = sss2
for q in q_list:
    res += dict_1.get(q, 0)
print(res)

Solution (Python):
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 = {}

    def rec(red, blue):
        if (red, blue) in cache:
            return cache[(red, blue)]
        nr = len(red)
        nb = len(blue)
        if nr > n or nb > n:
            res = 0
            cache[(red, blue)] = res
            return res
        if nr + nb == 2 * n:
            res = 1
            cache[(red, blue)] = res
            return res
        c = s[nr + nb]
        res = 0
        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()