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: Accepted

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

T1 = S[:N]
T2 = S[N:][::-1]

def window(i, P, L):
    if i == N:
        L.append(P)
        return L
    L = window(i+1, P+[0], L)
    L = window(i+1, P+[1], L)
    return L

L = window(0, [], [])
dic1 = {}
dic2 = {}
for mask in L:
    k1 = ''
    k2 = ''
    r1 = ''
    r2 = ''
    for i in range(N):
        if mask[i]:
            k1 += T1[i]
            k2 += T2[i]
        else:
            r1 += T1[i]
            r2 += T2[i]
    c1 = k1 + '_' + r1
    c2 = k2 + '_' + r2
    if not c1 in dic1.keys():
        dic1[c1] = 1
    else:
        dic1[c1] += 1
    if not c2 in dic2.keys():
        dic2[c2] = 1
    else:
        dic2[c2] += 1

ans = 0
for k1, v1 in dic1.items():
    if k1 in dic2.keys():
        ans += dic2[k1]*v1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def count(s, t1, t2):
    n = len(s)
    k1 = len(t1)
    k2 = len(t2)
    dp = [[0]*(k1+1) for i in range(n+1)]
    dp[0][0] = 1
    for i in range(n):
        for j in range(k1+1):
            # 次にt1を見るときは t1[j] を見る
            # 次にt2を見るときは t2[i-j]を見る
            if j+1 < k1+1 and t1[j] == s[i]:
                dp[i+1][j+1] += dp[i][j]
            if 0 <= i-j and i-j < k2 and  t2[i-j] == s[i]:
                dp[i+1][j] += dp[i][j]
    return dp[n][k1]

n = int(input())
s = input()
ss = s[n:]

m = 1 << n
ans = 0

for bit_state in range(m):
    red = []
    blue = []
    for i in range(n):
        if 1 << i & bit_state:
            red.append(s[i])
        else:
            blue.append(s[i])

    red = red[::-1]
    blue = blue[::-1]
    ans += count(ss, red, blue)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

T = [ord(S[i]) - 96 for i in range(N)]
U = [ord(S[i]) - 96 for i in range(2*N-1, N-1, -1)]


c1 = defaultdict(int)
c2 = defaultdict(int)

for i in range(1 << N) :
    a1, a2, b1, b2 = 0, 0, 0, 0
    for j in range(N) :
        if i & 1 :
            a1 = a1 * 27 + T[j]
            b1 = b1 * 27 + U[j]
        else :
            a2 = a2 * 27 + T[j]
            b2 = b2 * 27 + U[j]
        i >>= 1
        
    c1[(a1, a2)] += 1
    c2[(b1, b2)] += 1

ret = 0
for k, v in c1.items() :
    ret += v * c2[k]
print(ret)

Submission status: Accepted

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

T = S[:N]
U = S[N:]
U = U[::-1]

from collections import defaultdict

dd1 =defaultdict(int)
dd2 =defaultdict(int)

for i in range(2**N):
    red1 = ""
    blue1 = ""
    red2 = ""
    blue2 = ""
    for j in range(N):
        if (i//(2**j))%2==0:
            red1 = red1 + T[j]
            red2 = red2 + U[j]
        else:
            blue1 = blue1 + T[j]
            blue2 = blue2 + U[j]
    dd1[red1 + " " + blue1]+=1
    dd2[red2 + " " + blue2]+=1
ans=0
for key in dd1:
    ans+=dd1[key]*dd2[key]
print(ans)

Submission status: Accepted

Solution code:
import itertools
import os
import sys
from collections import defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

# 解説AC
N = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()


def test(N, S):
    import numpy as np
    S = np.array(list(S))
    ret = 0
    for r in itertools.combinations(range(N * 2), r=N):
        r = np.array(np.bincount(r, minlength=N * 2), dtype=bool)
        red = ''.join(S[r])
        blue = ''.join(S[~r])
        ret += red == blue[::-1]
    return ret


# print(test(N, S))

S, T = S[:N], S[:N - 1:-1]

t_counts = defaultdict(int)
for choice in itertools.product([0, 1], repeat=N):
    t = ''
    rev = ''
    for i, c in enumerate(choice):
        t += T[i] if c else ''
        rev += '' if c else T[i]
    t_counts[(t, rev)] += 1

ans = 0
for choice in itertools.product([0, 1], repeat=N):
    s = ''
    rev = ''
    for i, c in enumerate(choice):
        s += S[i] if c else ''
        rev += '' if c else S[i]
    ans += t_counts[(s, rev)]
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():

    return
#B
def B():

    return

#C
def C():
    n = I()
    s = S()
    for i in range(2*n):
        s[i] = ord(s[i])-96
    k = 27
    m = 1<<n
    p = [1<<j for j in range(n)]
    d = defaultdict(lambda : 0)
    l = [(0,0)]
    for i in s[:n][::-1]:
        l = [(x[0]*k+i, x[1]) for x in l]+[(x[0], x[1]*k+i) for x in l]
    for i in l:
        d[i] += 1
    ans = 0
    l = [(0,0)]
    for i in s[n:]:
        l = [(x[0]*k+i, x[1]) for x in l]+[(x[0], x[1]*k+i) for x in l]
    for i in l:
        ans += d[i]
    print(ans)
    return

#D
def D():

    return

#E
def E():

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():

    return
#B
def B():

    return

#C
def C():
    n = I()
    s = S()
    for i in range(2*n):
        s[i] = ord(s[i])-96
    for i in range(n>>1):
        s[i],s[n-i-1] = s[n-i-1],s[i]
    k = 27
    m = 1<<n
    p = [1<<j for j in range(n)]
    d = defaultdict(lambda : 0)
    for i in range(m):
        r = 0
        b = 0
        for j in range(n):
            if i&p[j]:
                r *= k
                r += s[j]
            else:
                b *= k
                b += s[j]
        d[(r,b)] += 1
    ans = 0
    for i in range(m):
        r = 0
        b = 0
        for j in range(n):
            if i&p[j]:
                r *= k
                r += s[j+n]
            else:
                b *= k
                b += s[j+n]
        ans += d[(r,b)]
    print(ans)
    return

#D
def D():

    return

#E
def E():

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():

    return
#B
def B():

    return

#C
def C():
    n = I()
    s = S()
    d = defaultdict(lambda : 0)
    alp = list("abcdefghijklmnopqrstuvwxyz")
    f = {}
    for i in range(26):
        f[alp[i]] = i+1
    for i in range(2*n):
        s[i] = f[s[i]]
    for i in range(n>>1):
        s[i],s[n-i-1] = s[n-i-1],s[i]
    k = 27
    m = 1<<n
    p = [1<<j for j in range(n)]
    for i in range(m):
        r = 0
        b = 0
        for j in range(n):
            if i&p[j]:
                r *= k
                r += s[j]
            else:
                b *= k
                b += s[j]
        d[(r,b)] += 1
    ans = 0
    for i in range(m):
        r = 0
        b = 0
        for j in range(n):
            if i&p[j]:
                r *= k
                r += s[j+n]
            else:
                b *= k
                b += s[j+n]
        ans += d[(r,b)]
    print(ans)
    return

#D
def D():

    return

#E
def E():

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

from collections import Counter

N = int(input())
S = input().rstrip()

left = [('','')]
for s in S[:N]:
    left = [(x[0]+s,x[1]) for x in left] + [(x[0],x[1]+s) for x in left]
left = [x+' '+y for x,y in left]
counter_L = Counter(left)

right = [('','')]
for s in S[N:][::-1]:
    right = [(x[0]+s,x[1]) for x in right] + [(x[0],x[1]+s) for x in right]
right = [x+' '+y for x,y in right]

answer = sum(counter_L[s] for s in right)
print(answer)

Submission status: Accepted

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

def main():
  n = int(input())
  s = input().strip()
  pc = defaultdict(lambda: 0)
  for i in range(pow(2, n)):
    rd = ""
    bl = ""
    for b in range(n):
      if (i // pow(2, b))%2 == 1:
        rd += s[b]
      else:
        bl += s[b]
    pc[(rd, bl)] += 1

  ans = 0
  s = s[::-1]
  for i in range(pow(2, n)):
    rd = ""
    bl = ""
    for b in range(n):
      if (i // pow(2, b)) % 2 == 1:
        bl += s[b]
      else:
        rd += s[b]
    ans += pc[(rd, bl)]

  print(ans)


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
S = input()
first = S[:N]
last = S[::-1][:N]

d = defaultdict(int)
ans = 0

def paint(str, ptn):
  p = ['', '']
  for i in range(N):
    p[int(2**i & ptn > 0)] += str[i]
  return tuple(p)

for i in range(2**N):
  d[paint(first, i)] += 1
  
for i in range(2**N):
  ans += d[paint(last, i)]
  
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
s1=s[:n]
s2=s[n:][::-1]
dic1={}
dic2={}
for i in range(2**n):
  r1=''
  r2=''
  b1=''
  b2=''
  flag=format(i,'b')
  l=len(flag)
  if l!=n:
    flag='0'*(n-l)+flag
  for j in range(n):
    if flag[j]=='0':
      r1+=s1[j]
      r2+=s2[j]
    else:
      b1+=s1[j]
      b2+=s2[j]
  if (r1,b1) not in dic1:
    dic1[(r1,b1)]=1
  else:
    dic1[(r1,b1)]+=1
  if (r2,b2) not in dic2:
    dic2[(r2,b2)]=1
  else:
    dic2[(r2,b2)]+=1
ans=0
for i in dic1.keys():
  if i in dic2:
    ans+=dic1[i]*dic2[i]
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

S1 = S[:N]
S2 = S[N:]
S2 = S2[::-1]
rb1 = Counter()
rb2 = Counter()
for i in range(2 ** N):
    flag = bin(i)[2:].zfill(N)
    r1 = ''
    b1 = ''
    r2 = ''
    b2 = ''
    for j in range(N):
        if flag[j] == '0':
            r1 += S1[j]
            r2 += S2[j]
        else:
            b1 = S1[j] + b1
            b2 = S2[j] + b2
    key1 = r1 + '&' + b1
    key2  =r2 + '&' + b2
    rb1[key1] += 1
    rb2[key2] += 1

ans = 0
for key in rb1.keys():
    ans += rb1[key] * rb2[key]

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
s = input().rstrip()
front = s[:n]
back = s[n:]
back = list(reversed(back))
front_cnt = Counter()
back_cnt = Counter()
for i in range(2**n):
    fred = fblue = bred = bblue = "" 
    for j in range(n):
        if(i & 1 << j):
            fred += front[j]
            bred += back[j]
        else:
            fblue += front[j]
            bblue += back[j]
    front_cnt[fred + "_" + fblue] += 1
    back_cnt[bred + "_" + bblue] += 1

ans = 0
for key in front_cnt.keys():
    ans += front_cnt[key] * back_cnt[key]
print(ans)

Submission status: Accepted

Solution code:
import itertools as it
from collections import Counter as c
n=int(input())
a=c()
b=c()
s=input()
q=s[:n]
r=s[n:][::-1]
for i in it.product([0,1],repeat=n):
    d,e,f,g="","","",""
    for j in range(n):
        if i[j]==1:
            d+=q[j]
            f+=r[j]
        else:
            e+=q[j]
            g+=r[j]
    a[d,e]+=1
    b[f,g]+=1
print(sum(a[i]*b[i] for i in a.keys()))

Submission status: Accepted

Solution code:
n = int(input())
s = list(input())
l = s[:n]
r = list(reversed(s[n:]))
hashl = {}
hashr = {}
for i in range(1 << n):
    llr = []
    llb = []
    lrr = []
    lrb = []
    for k in range(n):
        if i & (1 << k):
            llr.append(l[k])
            lrr.append(r[k])
        else:
            llb.append(l[k])
            lrb.append(r[k])
    sl = (''.join(llr), ''.join(llb))
    sr = (''.join(lrr), ''.join(lrb))

    if sl not in hashl: hashl[sl] = 1
    else: hashl[sl] += 1
    if sr not in hashr: hashr[sr] = 1
    else: hashr[sr] += 1
ret = 0
for strpair, c in hashl.items():
    if strpair in hashr:
        ret += hashr[strpair] * c
print(ret)

Submission status: Accepted

Solution code:
from itertools import product, compress
from collections import Counter

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

S1s = Ss[:N]
ptn1s = [''.join(compress(S1s, sels)) for sels in product(range(2), repeat=N)]
cnt1 = Counter([(red, blue) for red, blue in zip(ptn1s, reversed(ptn1s))])

S2s = Ss[N:][::-1]
ptn2s = [''.join(compress(S2s, sels)) for sels in product(range(2), repeat=N)]
cnt2 = Counter([(red, blue) for red, blue in zip(ptn2s, reversed(ptn2s))])

ans = 0
for ptn1, num1 in cnt1.items():
    ans += num1 * cnt2[ptn1]
print(ans)

Submission status: Accepted

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(S1) if 2**j & i])
    t2 = ''.join([s for j, s in enumerate(S1) if not 2**j & i])
    ans += H.get((t1, t2), 0)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def comb(s):
    p = deque([('','')])

    for i in range(len(s)):
        for j in range(2**i):
            e = p.pop()
            p.appendleft((e[0]+s[i],e[1]))
            p.appendleft((e[0],e[1]+s[i]))
    return p

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

sl = s[0:n]
sr = s[n:2*n][::-1]
keys1 = [c[0]+'-'+c[1] for c in comb(sl)]
keys2 = [c[0]+'-'+c[1] for c in comb(sr)]

dict = {}
for key1 in keys1:
    if key1 in dict:
        dict[key1] += 1
    else:
        dict[key1] = 1
cnt = 0
for key2 in keys2:
    if key2 in dict:
        cnt += dict[key2]

print(cnt)

Submission status: Accepted

Solution code:
from collections import defaultdict

n = int(input())
s = input()
s1 = s[:n]
s2 = s[n:][::-1]
def makeDic(s):
    dic = defaultdict(int)
    for i in range(2 ** n):
        mask = 1
        c1 = ""
        c2 = ""
        for j in range(n):
            if i & mask:
                c1 += s[j]
            else:
                c2 += s[j]
            mask <<= 1
        dic[(c1, c2)] += 1
    return dic


dic1 = makeDic(s1)
dic2 = makeDic(s2)
ans = 0
for key in dic1:
    if key in dic2:
        ans += dic1[key] * dic2[key]
print(ans)

Submission status: Accepted

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


def count(s):
    res = {}
    for i in range(2**N):
        t1 = ''
        t2 = ''
        for j in range(N):
            if i & 1 << j:
                t1 += s[j]
            else:
                t2 += s[j]
        k = t1 + t2 + 'abcdefghijklmnoprst'[bin(i).count('1')]
        res[k] = res.get(k, 0) + 1
    return res


h1 = count(S[:N])
h2 = count(S[N:][::-1])
ans = 0
for k, v in h1.items():
    if k in h2:
        ans += v * h2[k]
print(ans)

# https://www.youtube.com/watch?v=eB0eT-948Vw

Submission status: Accepted

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


def count(s):
    res = {}
    for i in range(2**N):
        t1 = ''
        t2 = ''
        for j in range(N):
            if i & 1 << j:
                t1 += s[j]
            else:
                t2 += s[j]
        k = t1 + t2[::-1] + str(bin(i).count('1'))
        res[k] = res.get(k, 0) + 1
    return res


h1 = count(S[:N])
h2 = count(S[N:][::-1])
ans = 0
for k, v in h1.items():
    if k in h2:
        ans += v * h2[k]
print(ans)

# https://www.youtube.com/watch?v=eB0eT-948Vw

Submission status: Accepted

Solution code:
N=int(input())
S=input()
Sf=S[:N]
Sb=S[N:2*N]
Sb=Sb[::-1]
ans=0
for i in range(2**N):
  R=[]
  B=[]
  for k in range(N):
    if i&(1<<k):
      R.append(Sf[k])
    else:
      B.append(Sf[k])
  dp=[[0]*(N+1) for i in range(N+1)]
  dp[0][0]=1
  f=True
  for k in range(1,N+1):
    for j in range(k):
      if j<len(R):
        if Sb[k-1]==R[j]:
          dp[k][j+1]+=dp[k-1][j]
      if 0<=k-j-1<len(B):
        if Sb[k-1]==B[k-j-1]:
          dp[k][j]+=dp[k-1][j]
  ans+=sum(dp[N])
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N=int(input())
S=input()
A=S[:N]
B=S[N:]
B=B[::-1]
def f(A):
    dd=defaultdict(int)
    for i in range(1<<N):
        a=[]
        b=[]
        for j in range(N):
            if i&(1<<j):
                a.append(A[j])
            else:
                b.append(A[j])
        s=''.join(a)
        t=''.join(b)
        dd[(s,t)]+=1
    return dd
dd1=f(A)
dd2=f(B)
ans=0
for t,c in dd1.items():
    ans+=dd2[t]*c
print(ans)

Submission status: Accepted

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

sa=s[:N]
sb=s[N:]

import itertools
ALLIST=itertools.product((0,1),repeat=N)

from collections import defaultdict
STRA = defaultdict(int)
STRB = defaultdict(int)

for i in ALLIST:
    red_a=""
    blue_a=""
    red_b=""
    blue_b=""
    for j in range(N):
        if i[j]==0:
            red_a+=sa[j]
            red_b+=sb[j]
        else:
            blue_a+=sa[j]
            blue_b+=sb[j]

    STRA[(red_a[::-1],blue_a[::-1])]+=1
    STRB[(red_b,blue_b)]+=1

ANS=0
for key in STRA:
    ANS+=STRA[key]*STRB[key]

print(ANS)

Submission status: Accepted

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

sa=s[:N]
sb=s[N:]

import itertools
ALLIST=list(itertools.product((0,1),repeat=N))

from collections import defaultdict
STRA = defaultdict(int)
STRB = defaultdict(int)

for i in ALLIST:
    red_a=""
    blue_a=""
    red_b=""
    blue_b=""
    for j in range(N):
        if i[j]==0:
            red_a+=sa[j]
            red_b+=sb[j]
        else:
            blue_a+=sa[j]
            blue_b+=sb[j]

    STRA[(red_a[::-1],blue_a[::-1])]+=1
    STRB[(red_b,blue_b)]+=1

ANS=0
for key in STRA:
    ANS+=STRA[key]*STRB[key]

print(ANS)

Submission status: Accepted

Solution code:
import itertools as I
from collections import Counter as C
n=int(input());s=input();l=s[:n];r=s[n:][::-1];a=C();b=C()
for i in I.product([0,1],repeat=n):
 t=u=v=w=''
 for j in range(n):
  if i[j]:t+=l[j];u+=r[j]
  else:v+=l[j];w+=r[j]
 a[t,v]+=1
 b[u,w]+=1
print(sum(a[i]*b[i]for i in a.keys()))

Submission status: Accepted

Solution code:
n=int(input());s=input();l=s[:n];r=s[n:][::-1];d={};e={}
for i in range(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
print(sum(d[i]*e.get(i,0)for i in d.keys()))

Submission status: Accepted

Solution code:
from itertools import product
from collections import defaultdict
n = int(input())
s = input()
sa, sb = s[:n], s[n:][::-1]
a, b, ans = defaultdict(int), defaultdict(int), 0
for p in product(range(2), repeat=n):
    word_a_1, word_b_1, word_a_2, word_b_2 = "", "", "", ""
    for j in range(n):
        if p[j]:
            word_a_1 += sa[j]
            word_b_1 += sb[j]
        else:
            word_a_2 += sa[j]
            word_b_2 += sb[j]
    a[(word_a_1, word_a_2)] += 1
    b[(word_b_1, word_b_2)] += 1
while a:
    key, value = a.popitem()
    ans += value * b[key]
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
from collections import defaultdict
n = int(input())
s = input()
sa,sb = s[:n],s[n:][::-1]
a,b,ans = defaultdict(int),defaultdict(int),0
for i in product(range(2),repeat=n):
	wa,wb,wa2,wb2 = "","","",""
	for j in range(n):
		if i[j]: wa,wb = wa+sa[j],wb+sb[j]
		else: wa2,wb2 = wa2+sa[j],wb2+sb[j]
	a[(wa,wa2)]+=1
	b[(wb,wb2)]+=1
while a:
	p,q = a.popitem()
	ans+=q*b[p]
print(ans)

Submission status: Accepted

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

sl = s[:n]
sr = s[n:][::-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 = [sr[i] for i in range(n) if not m[i]]
  key += ['-']
  key += [sr[i] for i in range(n) if m[i]]
  r[''.join(key)] += 1
  
ans = sum(l[lk] * r[lk] for lk in l.keys())

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N=int(input())
S=input()
A=S[:N]
B=S[N:]
B=B[::-1]
def f(A):
    dd=defaultdict(int)
    for i in range(1<<N):
        a=''
        b=''
        for j in range(N):
            if i&(1<<j):
                a+=A[j]
            else:
                b+=A[j]
        dd[(a,b)]+=1
    return dd
dd1=f(A)
dd2=f(B)
ans=0
for t,c in dd1.items():
    ans+=dd2[t]*c
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    s = S()
    s1 = s[:n]
    s2 = s[n:][::-1]
    d1 = collections.defaultdict(int)
    d2 = collections.defaultdict(int)
    ii = [2**_ for _ in range(n)]
    for i in range(2**n):
        t = t2 = t3 = t4 = ','
        for j in range(n):
            if ii[j] & i:
                t += s1[j]
                t3 += s2[j]
            else:
                t2 += s1[j]
                t4 += s2[j]
        d1[t+t2] += 1
        d2[t3+t4] += 1
    r = 0
    for k in d1.keys():
        r += d1[k] * d2[k]

    return r


print(main())

Submission status: Accepted

Solution code:
def run(n, s):
    '''
    文字列sを半分に分けて、右半分を逆順に並び替える
    さらに色の塗分けを逆にすると、左半分と右半分は
    同じになる
    '''
    sl = s[0:n]
    sr = s[n:2*n][::-1]

    keys1 = [c[0]+'-'+c[1] for c in comb(sl)]
    keys2 = [c[0]+'-'+c[1] for c in comb(sr)]
    dict = {}
    for key1 in keys1:
        if key1 in dict:
            dict[key1] += 1
        else:
            dict[key1] = 1
    cnt = 0
    for key2 in keys2:
        if key2 in dict:
            cnt += dict[key2]
    return cnt


def comb(s):
    if len(s) == 1:
        return [(s, ''), ('', s)]
    else:
        ret = []
        for c in comb(s[0:len(s)-1]):
            ret.append((c[0]+s[-1], c[1]))
            ret.append((c[0], c[1]+s[-1]))
        return ret


def read_line():
    n = int(input())
    s = input()
    return (n, s)


def main():
    n, s = read_line()
    print(run(n, s))


if __name__ == '__main__':
    main()

Submission status: Accepted

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)
    if (T0,T1) in L:
        L[(T0,T1)]+=1
    else:
        L[(T0,T1)]=1
    if (T2,T3) in R:
        R[(T2,T3)]+=1
    else:
        R[(T2,T3)]=1
for tup in L:
    if tup in R:
        ans+=L[tup]*R[tup]
print(ans)

Submission status: Accepted

Solution code:
import itertools
import bisect
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)
    if (T0,T1) in L:
        L[(T0,T1)]+=1
    else:
        L[(T0,T1)]=1
    if (T2,T3) in R:
        R[(T2,T3)]+=1
    else:
        R[(T2,T3)]=1
for tup in L:
    if tup in R:
        ans+=L[tup]*R[tup]
print(ans)

Submission status: Accepted

Solution code:
def run(n, s):
    '''
    文字列sを半分に分けて、右半分を逆順に並び替える
    さらに色の塗分けを逆にすると、左半分と右半分は
    同じになる
    '''
    sl = s[0:n]
    sr = s[n:2*n][::-1]

    dic = {}
    keys = []
    cnt = 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 += sl[j]
                red2 += sr[j]
            else:
                blue += sl[j]
                blue2 += sr[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:
        cnt += dic.get(key, 0)
    return cnt

    '''
    keys1 = [c[0]+'-'+c[1] for c in comb(sl)]
    keys2 = [c[0]+'-'+c[1] for c in comb(sr)]
    cnt = 0
    for key1 in keys1:
        cnt += keys2.count(key1)
    return cnt
    '''
    '''
    dict = {}
    for t0, t1 in keys:
        key = t0 + '-' + t1
        cnt = has_key(sr, t0, t1)
        if key in dict:
            dict[key] += cnt
        else:
            dict[key] = cnt
    return sum(dict.values())
    '''


'''
def comb(s):
    if len(s) == 1:
        return [(s, ''), ('', s)]
    else:
        ret = []
        for c in comb(s[0:len(s)-1]):
            ret.append((c[0]+s[-1], c[1]))
            ret.append((c[0], c[1]+s[-1]))
        return ret
'''


'''
def has_key(s, t0, t1):
    cnt = 0
    if len(s) == 1:
        if s == t0:
            return 1
        elif s == t1:
            return 1
        else:
            return 0
    else:
        a = s[0]
        if len(t0) != 0 and a == t0[0]:
            cnt += has_key(s[1:len(s)], t0[1:len(t0)], t1)
        if len(t1) != 0 and a == t1[0]:
            cnt += has_key(s[1:len(s)], t0, t1[1:len(t1)])
    return cnt
'''


def read_line():
    n = int(input())
    s = input()
    return (n, s)


def main():
    n, s = read_line()
    print(run(n, s))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#coding: utf-8
# C: String Coloering
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))))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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] #bitに1が立っているところを赤に
      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] #同じkey(分け方）に対するredとblueの通りを掛け合わせる
print(answer)