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: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
S = input()
countp = defaultdict(int)
counts = defaultdict(int)
prefix = S[:N]
suffix = S[2*N-1:N-1:-1]
for i in range(1 << (N - 1)):
    p1 = ''
    s1 = ''
    p2 = ''
    s2 = ''
    for j in range(N):
        if (1 << j) & i:
            p1 += prefix[j]
            s1 += suffix[j]
        else:
            p2 += prefix[j]
            s2 += suffix[j]
    countp[(p1, p2)] += 1
    countp[(p2, p1)] += 1
    counts[(s1, s2)] += 1
    counts[(s2, s1)] += 1
    

print(countp, counts)

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

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
S1, S2 = S[: N], S[2*N-1: N-1: -1]
hash_S1, hash_S2 = {}, {}

for i in range(1<<N): # 赤に塗られた箇所が1
    red = []
    blue = []
    for j in range(N):
        if i >> j & 1:
            red.append(S1[j])
        else:
            blue.append(S1[j])
    
    key = ''.join(blue) + '+' + ''.join(red)
    if key in hash_S1:
        ans += hash_S1[key]

ans = 0
for i in range(1<<N): # 赤に塗られた箇所が1
    red = []
    blue = []
    for j in range(N):
        if i >> j & 1:
            red.append(S2[j])
        else:
            blue.append(S2[j])
    
    key = ''.join(blue) + '+' + ''.join(red)
    if key in hash_S1:
        ans += hash_S1[key]

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n = int(input())
s = input()

a = s[:n]
b = s[n:][::-1]
print(a, b)
d = defaultdict(int)
e = defaultdict(int)


def cnt(c, d):
    for bit in range(1 << n):
        x = []
        y = []
        for i in range(n):
            if bit >> i & 1:
                x.append(c[i])
            else:
                y.append(c[i])
        d[(str(x), str(y))] += 1


cnt(a, d)
cnt(b, e)

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline

n = int(input())
S = input()
L = S[:n]
R = S[n:][::-1]
C = defaultdict(int)
ans = 0
for i in range(1<<n):
  l = ""
  r = ""
  for j, s in enumerate(L):
    if i>>j & 1:
      l += s
    else:
      r += s
  C[l+"."+r] += 1
for i in range(1<<n):
  l = ""
  r = ""
  for j, s in enumerate(R):
    if i>>j & 1:
      l += s
    else:
      r += s
  ans += C[l+"."+r]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10


N = INT()
S = input()

former = S[:N]
latter = S[N:][::-1]

dic_f = defaultdict(int)
dic_l = defaultdict(int)

for x in product([0, 1], repeat=N):
	tmp_red = ""
	tmp_blue = ""
	for i in range(N):
		if x[i]:
			tmp_red += former[i]
		else:
			tmp_blue += former[i]
	dic_f["{},{}".format(tmp_red, tmp_blue)] += 1

for x in product([0, 1], repeat=N):
	tmp_red = ""
	tmp_blue = ""
	for i in range(N):
		if x[i]:
			tmp_red += latter[i]
		else:
			tmp_blue += latter[i]
	dic_l["{},{}".format(tmp_red, tmp_blue)] += 1

ans = 0

for key in dic_f:
	red_f, blue_f = key.split(",")
	ans += dic_l["{},{}".format(blue_f, red_f)]

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
from collections import defaultdict

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

d = defaultdict(int)
left = set()

for r in range(n + 1):
	for j in combinations(range(n), r):
		sl = ""
		sr = ""
		for i in range(n):
			if i in j:
				sl += s[i]
			else:
				sr += s[i]
		left.add(sl + "," + sr)
		d[sl + "," + sr] += 1
res = 0
for r in range(n + 1):
	for j in combinations(range(n, 2 * n), r):
		sl = ""
		sr = ""
		for i in range(n, n):
			if i in j:
				sl = s[i] + sl
			else:
				sr = s[i] + sr
		if sr + "," + sl in left:
			res += d[sr + "," + sl]
print(res)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd

n = int(input())
_s = list(map(ord, list(input())))
s,t = _s[:n], _s[:n-1:-1]
d = dict()
mod = 10**9 + 9

def get(st):
  for bit in range(1<<n):
    u = v = 0
    for j,e in enumerate(s):
      if bit & (1<<j):
        u = (u*100 + e)%mod
      else:
        v = (v*100 + e)%mod
    yield (u,v)

ans = 0
d = dd(int)
for x in get(s): d[x] += 1
for x in get(t): ans += d[x]
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
n = int(input())
s = input()
ls = []
tmp = []
for i in range(1,2**(2*n)//2-1):
    tmp = list(bin(i)[2:].zfill(n*2))
    c = collections.Counter(tmp)
    common = c.most_common()
    if common[0][1] == n:
        ls.append(tmp)
        
#ls = [bin(i)[2:].zfill(n*2) for i in range(1,2**(2*n)-1)]

ans = 0
for i in ls:
    red = []
    blue = []
    for j in range(2*n):
        if i[j] == '1':
            red.append(s[j])
    for k in range(2*n):
        if i[-k-1] == '0':
            blue.append(s[-k-1])
    if red == blue:
        ans += 1
print(ans*2)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
S1 = S[:N]
S2 = S[N::][::-1]
H = dict()
for i in range(2**N):
    t1 = ''.join([s for j, s in enumerate(S2) if 2**j & i])
    t2 = ''.join([s for j, s in enumerate(S2) if not 2**j & i])
    k = H.get((t1, t2), 0)
    H[(t1, t2)] = k+1
ans = 0
for i in range(2**N):
    t1 = ''.join([s for j, s in enumerate(S2) if 2**j & i])
    t2 = ''.join([s for j, s in enumerate(S2) if not 2**j & i])
    ans += H.get((t1, t2), 0)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
s=list(input())
l=s[:n]
r=s[n:][::-1]
d={}
e={}
for i in range(1,1<<n):
  s=t=u=v=''
  for j in range(n):
    if (i>>j)&1:
      s+=l[j]
      t+=r[j]
    else:
      u+=l[j]
      v+=r[j]
  d[(s,u)]=d.get((s,u),0)+1
  e[(t,v)]=e.get((t,v),0)+1
a=0
for i in d.keys():
  a+=d[i]*e.get(i,0)
print(a)

Submission status: Wrong Answer

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

sl = s[:n]
sr = s[:n-1:-1]

from collections import Counter
l = Counter()
r = Counter()

from itertools import product
for m in product([False, True], repeat=n):
  key = [sl[i] for i in range(n) if not m[i]]
  key += ['-']
  key += [sl[i] for i in range(n) if m[i]]
  l[''.join(key)] += 1
  
  key = ''.join([sr[i] for i in range(n) if not m[i]])
  key += '-'
  key += ''.join([sr[i] for i in range(n) if m[i]])
  r[key] += 1
  
ans = sum(l[lk] * r[lk] for lk in l.keys())
print(l)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N=int(input())
S=input()
ans=0
L=dict()
R=dict()
for seq in itertools.product([0,1],repeat=N):
    T0=""
    T1=""
    T2=""
    T3=""
    for i in range(N):
        if seq[i]==0:
            T0+=S[i]
            T2+=S[-i-1]
        else:
            T1+=S[i]
            T3+=S[-i-1]
    a0=len(T0)
    a1=len(T1)
    a2=len(T2)
    a3=len(T3)
    L[(T0,T1)]=L.get((T0,T1),0)+1
    R[(T0,T1)]=R.get((T0,T1),0)+1
for tup in L:
    if tup in R:
        ans+=L[tup]*R[tup]
print(ans)

Submission status: Wrong Answer

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

'''
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: Wrong Answer

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,D2 = {},{}

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 not in D2.keys():
        D2[key] = 1
    else:
        D2[key] += 1

Ans = 0
for key1 in D1:
    i,s = key1
    key2 = (N-i,s)
    if key2 in D2.keys():
        Ans += D1[key1] * D2[key2]

print(Ans)

Submission status: Wrong Answer

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[-i])
    else:
      bs1.append(S[i])
      bs2.append(S[-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: Wrong Answer

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

def find(A,B,lst):
	q = (B,A)
	l,r = 0, len(lst)
	while r - l > 1:
		nxt = (l + r) // 2
		print(l,r,nxt,lst[nxt],q)
		if lst[nxt] < q:
			l = nxt
		else:
			r = nxt
	print(lst[l],q)
	if lst[l] >= q:
		return l 
	else:
		return r
MAX = 2 ** N
ans = 0
first = [S[i] for i in range(N)]
last = [S[i] for i in range(N,2*N)]

search = []
lasts = [[] for i in range(N+1)]

for i in range(MAX):
	paint = [False for i in range(N)]
	n = i
	c = 0
	while n > 0:
		paint[c] = (n%2 == 1)
		c += 1
		n = n // 2
	A = "".join([first[i] for i in range(N) if paint[i]])
	B = "".join([first[N-i] for i in range(1, N+1) if not paint[N-i]])
	search.append((A,B))

	cnt = sum([1 if p else 0 for p in paint])
	A = "".join([last[i] for i in range(N) if paint[i]])
	B = "".join([last[N-i] for i in range(1, N+1) if not paint[N-i]])
	lasts[cnt].append((A,B))

for i in range(N):
	lasts[i].sort()

for A,B in search:
	len_B = len(B)
	if len_B > 0 and len_B < N:
		a = list(A)
		a[len(a)-1] = chr(ord(a[len(a)-1]) + 1)
		A2 = "".join(a)
		i1 = find(A,B,lasts[len_B])
		i2 = find(A2,B,lasts[len_B])
		print(B,A,A2,lasts[len_B],i2,i1)
		ans += i2 - i1
	elif (B,A) == lasts[len_B][0]:
		ans += 1
print(ans)

Submission status: Wrong Answer

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
        if not flg: break
        dp = dp2

    ans += dp[lenF]

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

n = int(input())
s = list(input())
s1 = [i for i in range(1,2*n)]
a = list(itertools.combinations(s1,n-1))
res = 0
print(a)

for i in range(len(a)):
    k = list(a[i])
    k.insert(0, 0)
    b = list(set(s1)-set(k))
    b.reverse()
    a1 = [s[i] for i in k]
    b1 = [s[i] for i in b]
    if a1 == b1:
        res += 1
print(res*2)

Submission status: Wrong Answer

Solution code:

import sys
#sys.stdin=open("data.txt")
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 b=="":
        if a=="" and c=="": return 1
        else: return 0
    key=a+"/"+b+"/"+c
    if key in memo: return memo[key]
    # select first letter
    ans=0
    for i in range(1,len(b)):
        if b[0]==b[i]:
            ans+=getans(a,b[1:i],b[i+1:]+c)
    # don't select first letter
    ans+=getans(a+b[0],b[1:],c)
    memo[key]=ans
    #print(key,ans)
    return ans

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

print(len(memo))

Submission status: Time Limit Exceeded

Solution code:
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[::-1][:N]
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 (b1,r1),v1 in ctr1.items():
    for (b2,r2),v2 in ctr2.items():
        if b1==r2 and b2==r1:
            ans += v1*v2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict
from itertools import compress 
N = int(input())
S = input()
S1,S2 = S[:N],S[N:]

Ls = defaultdict(lambda : defaultdict(int))
Rs = defaultdict(lambda : defaultdict(int))

def int2bin(x,N): 
    res = [0]*N
    for i in range(N):
        res[N-1-i] = x % 2
        x >>= 1
    return res

for i in range(2**N):
    bs = int2bin(i,N)
    n = sum(bs)
    R = ""
    L = ""
    for s,b in zip(S1,bs):
        if b == 1:
            R += s
        else:
            L += s
    Ls[n][(R,L[::-1])] += 1
    R = ""
    L = ""
    for s,b in zip(S2,bs):
        if b == 1:
            R += s
        else:
            L += s
    Rs[n][(R,L[::-1])] += 1

ans = 0
for i in range(N+1):
    for (lr,lb),n in Ls[i].items():
        for (rr,rb),m in Rs[N-i].items():
            if lr+rr == rb+lb:
                ans += n*m

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
from collections import defaultdict
l,r=s[:n],s[-1:-n-1:-1]

def g(l,n):
    b=set(range(n))
    d=defaultdict(int)
    for i in range(2**n):
        a={j for j in range(n)if (i>>j)%2}
        abar=b-a
        d[("".join(l[p] for p in sorted(list(a))),"".join(l[o] for o in sorted(list(abar))))]+=1
    return d
f,c=g(l,n),g(r,n)
#print(f,c,sep="\n")
print(sum(f[k]*c[k] for k in f))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=list(input())
a,b=s[n-1::-1],s[n:]

ad={}
bd={}
for i in range(2**n):
    sa=tuple(a[j]for j in range(n)if (i>>j)%2)
    ta=tuple(a[j]for j in range(n)if (i>>j)%2==0)
    sb=tuple(b[j]for j in range(n)if (i>>j)%2)
    tb=tuple(b[j]for j in range(n)if (i>>j)%2==0)
    if (sa,ta)in ad:ad[(sa,ta)]+=1
    else:ad[(sa,ta)]=1
    if (sb,tb)in bd:bd[(sb,tb)]+=1
    else:bd[(sb,tb)]=1
ans=0
for k in ad:
    if k in bd:
        ans+=bd[k]*ad[k]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return (int(x) for x in input().split())
def LI(): return list(Is())
def TI(): return tuple(Is())
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(S())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = 10**18
# ----------------------------------------------------------- #

n = I()
s = S()
sa = s[:n]
sb = s[n:][::-1]

A = defaultdict(int)
B = defaultdict(int)

for bit in range(1<<n):
    red_A = []
    red_B = []
    blue_A = []
    blue_B = []
    for i in range(n):
        if bit & 1<<i:
            red_A.append(sa[i])
            blue_B.append(sb[i])
        else:
            blue_A.append(sa[i])
            red_B.append(sb[i])
    a_key = (''.join(red_A), ''.join(blue_A))
    b_key = (''.join(blue_B), ''.join(red_B))
    A[a_key] += 1
    B[b_key] += 1

ans = 0
for key in A.keys():
    if key in B.keys():
        ans += A[key]*B[key]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce, lru_cache  # @lru_cache(None)
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return (int(x) for x in input().split())
def LI(): return list(Is())
def TI(): return tuple(Is())
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(S())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = 10**18
# ----------------------------------------------------------- #

n = I()
s = S()
sa = s[:n]
sb = s[n:][::-1]

A = defaultdict(int)
B = defaultdict(int)

for bit in range(1<<n):
    red_A = ""
    red_B = ""
    blue_A = ""
    blue_B = ""
    for i in range(n):
        if bit & 1<<i:
            red_A += sa[i]
            blue_B += sb[i]
        else:
            blue_A += sa[i]
            red_B += sb[i]
    A[(red_A, blue_A)] += 1
    B[(blue_B, red_B)] += 1

ans = 0
for key in A.keys():
    if key in B.keys():
        ans += A[key]*B[key]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n = int(input())
s = input()
ls = s[:n:]
rs = s[:n-1:-1]
dl = defaultdict(int)
dr = defaultdict(int)

for i in range(2**n):
    lr = ""
    rr = ""
    lb = ""
    rb = ""
    ii = i
    for j in range(n):
        if ii&1 == 1:
            lr += ls[j]
            rr += rs[j]
        else:
            lb += ls[j]
            rb += rs[j]
        ii >>= 1
    dl[(lr,lb)] += 1
    dr[(rr,rb)] += 1

ans = 0
for dlk,dlv in dl.items():
    ans += dlv*dr[dlk]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
ls = s[:n:]
rs = s[:n-1:-1]
dl = dict()
dr = dict()

for i in range(2**n):
    lr = ""
    rr = ""
    lb = ""
    rb = ""
    ii = i
    for j in range(n):
        if ii&1 == 1:
            lr += ls[j]
            rr += rs[j]
        else:
            lb += ls[j]
            rb += rs[j]
        ii >>= 1
    dl[(lr,lb)] = dl.get((lr,lb),0)+1
    dr[(rr,rb)] = dr.get((rr,rb),0)+1

ans = 0
for dlk,dlv in dl.items():
    ans += dlv*dr.get(dlk,0)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
ls = s[:n:]
rs = s[:n-1:-1]
dl = dict()
dr = dict()

for i in range(2**n):
    lr = ""
    rr = ""
    lb = ""
    rb = ""
    ii = i
    for j in range(n):
        if ii%2 == 1:
            lr += ls[j]
            rr += rs[j]
        else:
            lb += ls[j]
            rb += rs[j]
        ii >>= 1
    dl[(lr,lb)] = dl.get((lr,lb),0)+1
    dr[(rr,rb)] = dr.get((rr,rb),0)+1

ans = 0
for dlk,dlv in dl.items():
    ans += dlv*dr.get(dlk,0)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N,S = open(0).read().split()
N = int(N)
ldic = defaultdict(int)
rdic = defaultdict(int)
L = S[:N]
R = S[N:][::-1]
for i in range(2**N):
  la = ''
  lb = ''
  ra = ''
  rb = ''
  for j in range(N):
    if i%2==1:
      la += L[j]
      ra += R[j]
    else:
      lb += L[j]
      rb += R[j]
    i >>= 1
  ldic[(la,lb)] += 1
  rdic[(ra,rb)] += 1
ans = sum(rdic[k]*ldic[k] for k in ldic.keys())
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
S = input()
s1 = S[:n];s2 = S[n:][::-1]
C1 = collections.Counter()
C2 = collections.Counter()
for bit in range(2**n):
  tmp10 = ""
  tmp11 = ""
  tmp20 = ""
  tmp21 = ""
  for i in range(n):
    if bit >> i & 1:
      tmp10 += s1[i]
      tmp20 += s2[i]
    else:
      tmp11 += s1[i]
      tmp21 += s2[i]
  C1[(tmp10,tmp11)] += 1
  C2[(tmp21,tmp20)] += 1
for key,item in C1.items():
  ans += C2[key] * item 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

dic = defaultdict(int)

for i in range(2 ** N):
    a = str()
    b = str()
    for j in range(N):
        if (i >> j) & 1:
            a += S[j + N]
        else:
            b += S[j + N]
    
    dic[(a, b)] += 1

count = 0
for i in range(2 ** N):
    a = str()
    b = str()
    for j in range(N):
        if (i >> j) & 1:
            a += S[j]
        else:
            b += S[j]
    count += dic[b[::-1], a[::-1]]

print (count)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    S = tuple(input())

    def check(red, blue): #赤色、青色がわかるリストが与えられる。
        max_n = len(blue) #青色の個数 = 赤色の後ろにつける個数
        max_r = len(red)
        dp = [[[-1] * (max_n + 1) for _ in range(max_r + 1)] for _ in range(N + 1)]
        
        def calc(i, tmp, n):
            if i == N - 1:
                return 1

            if dp[i - N][tmp][n] != -1:
                return dp[i - N][tmp][n]

            tmp_count = 0
            if n < max_n and S[i] == S[blue[n]]:
                tmp_count += calc(i - 1, tmp, n + 1)
            if tmp < max_r and S[i] == S[red[tmp]]:
                tmp_count += calc(i - 1, tmp + 1, n)
            
            dp[i - N][tmp][n] = tmp_count
            return tmp_count

        return calc(2 * N - 1, 0, 0)
        # for i in range(2 * N - 1, N - 1, -1): #後半部分を後ろから探索
        #     # print (i, n - 1, blue[n - 1])
        #     if n < max_n and S[i] == S[blue[n]]: #青色と一致しているとき
        #         n += 1
        #     else:
        #         if tmp < len(red) and S[i] == S[red[tmp]]:
        #             tmp += 1
        #         else:
        #             return False
        # return True


    count = 0
    for i in range(2 ** N):
        red = []
        blue = []
        # lst = [0] * N #0: 赤色、1: 青色
        for j in range(N):
            if (i >> j) & 1:
                red.append(j)
                # lst[j] = 1
            else:
                blue.append(j)
        
        # print (check(red, blue), red, blue)
        count += check(red, blue)

    print (count)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def check(red, blue): #赤色、青色がわかるリストが与えられる。
    max_n = len(blue) #青色の個数 = 赤色の後ろにつける個数
    max_r = len(red)
    dp = [[[-1] * (max_n + 1) for _ in range(max_r + 1)] for _ in range(N + 1)]
    
    def calc(red, blue, i, tmp, n):
        if i == N - 1:
            return 1

        if dp[i - N][tmp][n] != -1:
            return dp[i - N][tmp][n]

        tmp_count = 0
        if n < max_n and S[i] == S[blue[n]]:
            tmp_count += calc(red, blue, i - 1, tmp, n + 1)
        if tmp < max_r and S[i] == S[red[tmp]]:
            tmp_count += calc(red, blue, i - 1, tmp + 1, n)
        
        dp[i - N][tmp][n] = tmp_count
        return tmp_count

    return calc(red, blue, 2 * N - 1, 0, 0)
    # for i in range(2 * N - 1, N - 1, -1): #後半部分を後ろから探索
    #     # print (i, n - 1, blue[n - 1])
    #     if n < max_n and S[i] == S[blue[n]]: #青色と一致しているとき
    #         n += 1
    #     else:
    #         if tmp < len(red) and S[i] == S[red[tmp]]:
    #             tmp += 1
    #         else:
    #             return False
    # return True


count = 0
for i in range(2 ** N):
    red = []
    blue = []
    lst = [0] * N #0: 赤色、1: 青色
    for j in range(N):
        if (i >> j) & 1:
            red.append(j)
            lst[j] = 1
        else:
            blue.append(j)
    
    # print (check(red, blue), red, blue)
    count += check(red, blue)

print (count)

Submission status: Time Limit Exceeded

Solution code:

from collections import defaultdict


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

X = S[:N]
Y = S[N:]
Y = Y[::-1]

dx = defaultdict(int)
dy = defaultdict(int)

for bit in range(1 << N):
    red = ""
    blue = ""
    for i in range(N):
        if bit & (1 << i):
            red += X[i]
        else:
            blue += X[i]

    dx[(red, blue)] += 1

for bit in range(1 << N):
    red = ""
    blue = ""
    for i in range(N):
        if bit & (1 << i):
            red += Y[i]
        else:
            blue += Y[i]

    dy[(red, blue)] += 1

# 前後が同じになる組がいくつできるか。
ans = 0
for k,v in dx.items():
    ans += dy[k] * v

print(ans)

Submission status: Time Limit Exceeded

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n = ii()
s = input().rstrip()
dic = {}

for mask in range(1<<n):
    a = ""
    b = ""
    for i in range(n):
        if (mask&1<<i) :a += s[i]
        else :b += s[i]
    c = a + "0" + b
    dic.setdefault(c,0)
    dic[c] += 1

ans = 0

for mask in range(1<<n):
    a = ""
    b = ""
    for i in range(n):
        if (mask&1<<i) :a += s[2*n - 1 - i]
        else :b += s[2*n -1 -i]
    c = a + "0" + b
    dic.setdefault(c,0)
    ans += dic[c]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
n = int(input())
s = input()

res = 0
for cl in combinations(range(2*n),n):
    sl = []
    for i in cl:
        sl.append(s[i])
    sr = []
    for i in range(2*n):
        if i in cl:
            continue
        sr.append(s[i])
    valid = True
    for i in range(n):
        if sl[i]!=sr[n-1-i]:
            valid = False
            break
    if valid:
        res += 1

print(res)

Submission status: Time Limit Exceeded

Solution code:
import collections
from collections import deque
n = int(input())
s = input()
ls = []
tmp = []
for i in range(1,2**(2*n)//2):
    tmp = list(bin(i)[2:].zfill(n*2))
    if tmp.count('0') == n:
        ls.append(tmp)
        
#ls = [bin(i)[2:].zfill(n*2) for i in range(1,2**(2*n)-1)]

ans = 0
for i in ls:
    red = []
    blue = deque()
    for j in range(2*n):
        if i[j] == '1':
            red.append(s[j])
        else:
            blue.appendleft(s[j])
    if red == list(blue):
        ans += 1
print(ans*2)

Submission status: Time Limit Exceeded

Solution code:
import collections
n = int(input())
s = input()
ls = [bin(i)[2:].zfill(n*2) for i in range(1,2**(2*n)-1)]

ans = 0
for i in ls:
    c = collections.Counter(i)
    common = c.most_common()
    if common[0][1] == common[1][1]:
        red = []
        blue = []
        for j in range(2*n):
            if i[j] == '1':
                red.append(s[j])
        for k in range(2*n):
            if i[-k-1] == '0':
                blue.append(s[-k-1])
        if red == blue:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n = int(input())
S = input()
A = S[:n]
B = S[n:][::-1]
Da = defaultdict(int)
Db = defaultdict(int)
ans = 0
for i in range(2**n):
  a1, a2 = "", ""
  for j in range(n):
    if i>>j & 1:
      a1 += A[j]
    else:
      a2 += A[j]
  Da[(a1, a2)] += 1
for i in range(2**n):
  b1, b2 = "", ""
  for j in range(n):
    if i>>j & 1:
      b1 += B[j]
    else:
      b2 += B[j]
  Db[(b1, b2)] += 1

for k in Da:
  ans += Da[k] * Db[k]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
S = input()

S1 = S[:N]
# 左右同じものを目指す形にしたいので、片方はリバースしておく
S2 = S[N:][::-1]

d1 = Counter()
d2 = Counter()
# 半分に分けた両方を組み合わせ全列挙
for i in range(1<<N):
    s1_1, s1_2 = '', ''
    s2_1, s2_2 = '', ''
    for j in range(N):
        if i>>j & 1:
            s1_1 += S1[j]
            s2_1 += S2[j]
        else:
            s1_2 += S1[j]
            s2_2 += S2[j]
    # 文字列ペアをキーとして、その通り数を数えておく
    d1[(s1_1, s1_2)] += 1
    d2[(s2_1, s2_2)] += 1

ans = 0
for k, v in d1.items():
    # 左文字列ペア = 右文字列ペア になるような通り数を数え上げる
    ans += v * d2[k]
print(ans)