Problem:


Score : 600 points

Problem Statement

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

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

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

Constraints

1 \leq N \leq 18

The length of S is 2N.

S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

N
S

Output

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

Sample Input 1

4
cabaacba

Sample Output 1

4

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

cabaacba

cabaacba

cabaacba

cabaacba

Sample Input 2

11
mippiisssisssiipsspiim

Sample Output 2

504

Sample Input 3

4
abcdefgh

Sample Output 3

0

Sample Input 4

18
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Sample Output 4

9075135300

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



Sample input:
4
cabaacba


Sample output:
4

Submission status: Time Limit Exceeded

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

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

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

    memo = {}

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

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

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

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

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

    return ans


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

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

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

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

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

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

Submission status: Time Limit Exceeded

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

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

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

    d = collections.defaultdict(set)
    for i in xrange(2*n):
        d[s[i]].add(i)

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

        if sorted(s) != sorted(blue+red+b+r): continue

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

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

        ans += dp[-1][-1][-1]

    return ans


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

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
import math

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

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

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

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

def hantei(s, mask):
    for c in count:
        if count[c] % 2 != 0:
            return False
    a, b = split(s, mask)
    b = b[::-1]
    if a == b:
        return True
    return False

res = 0

count = strcount(s)
if len(count) == 1:
    res = combinations_count(2 * n, n)
else:
    i = 0
    for mask in combinations(range(2 * n), n):
        if i >= combinations_count(2 * n, n) // 2:
            break
        if hantei(s, mask):
            res += 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product, compress

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

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

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

    lenF = len(Fs)
    lenG = N - lenF
    dp = [1] + [0] * lenF
    for i, s in enumerate(Ss[N:], 1):
        dp2 = [0] * (lenF + 1)
        for j in range(lenF + 1)[::-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]
        dp = dp2

    ans += dp[lenF]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product, compress

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

ans = 0
for sels in product([0, 1], repeat=N):
    Fs = list(compress(Ss[:N], sels))[::-1]
    Gs = list(compress(Ss[:N], map(lambda x: 1-x, sels)))[::-1]

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

    ans += dp[N][lenF]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import queue
N=int(input())
S=input()
ans=0
for seq in itertools.product([0,1],repeat=N):
    T0=""
    T1=""
    T2=""
    for i in range(N):
        if seq[i]==0:
            T0=T0+S[i]
        else:
            T1=T1+S[i]
        T2+=S[-i-1]
    q=[queue.Queue() for i in range(N+1)]
    q[0].put((0,0))
    a0=len(T0)
    a1=len(T1)
    #print(T0,T1,T2)
    for i in range(N):
        while(not(q[i].empty())):
            r=q[i].get()
            #print(i,r)
            #print(r)
            if r[0]+r[1]>=N:
                continue
            if r[0]>=a0:
                if T2[r[1]+r[0]]==T1[r[1]]:
                    q[i+1].put((r[0],r[1]+1))
            elif r[1]>=a1:
                if T2[r[1]+r[0]]==T0[r[0]]:
                    q[i+1].put((r[0]+1,r[1]))
            else:
                if T2[r[1]+r[0]]==T0[r[0]]:
                    q[i+1].put((r[0]+1,r[1]))
                if T2[r[1]+r[0]]==T1[r[1]]:
                    q[i+1].put((r[0],r[1]+1))
    while(not(q[N].empty())):
        r=q[N].get()
        #print(N,r)
        ans+=1
        #print(ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
S = input()
T = ["","",S]
D = deque([T])
count = 0
while(len(D)>0):
    tmpT = D.pop()
    tmpT1 = [tmpT[0],tmpT[1],tmpT[2][1:]]
    tmpT2 = [tmpT[0],tmpT[1],tmpT[2][1:]]
    tmpT1[0]+=tmpT[2][0]
    tmpT2[1]=tmpT[2][0]+tmpT2[1]
    if len(tmpT1[0])+len(tmpT1[1]) == 2*N:
        if tmpT1[0] == tmpT1[1]:
            count+=1
    elif len(tmpT1[0]) <= N and len(tmpT1[1]) <= N:
        D.append(tmpT1)
    if len(tmpT2[0])+len(tmpT2[1]) == 2*N:
        if tmpT2[0] == tmpT2[1]:
            count+=1
    elif len(tmpT2[0]) <= N and len(tmpT2[1]) <= N:
        D.append(tmpT2)
print(count)

Submission status: Time Limit Exceeded

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

dict_1 = dict()

res = 0

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = list(input()) 
ref = 0
list_b = [S[0]]
list_r = ['']
for i in range(len(S)):
    new_list_b = []
    new_list_r = []
    if i == 0:
        continue
    else:
        for j in  range(len(list_b)):
            new_list_b.append(list_b[j] + S[i])
            new_list_r.append(list_r[j])
            if len(new_list_b[-1])>N:
                new_list_b.pop(-1)
                new_list_r.pop(-1)
            new_list_b.append(list_b[j])
            new_list_r.append(list_r[j] + S[i])
            if len(new_list_r[-1])>N:
                new_list_b.pop(-1)
                new_list_r.pop(-1)            
    list_b = new_list_b
    list_r = new_list_r
for i in range(len(list_b)):
    if list_b[i] == list_r[i][::-1]:
        ref += 1
print(2 * ref)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
S_l = S[:N]
S_r = S[N:][::-1]
dict_l = {}
dict_r = {}
ans = 0
for num in range(2**N):
  tmpl_1 = ""
  tmpl_2 = ""
  tmpr_1 = ""
  tmpr_2 = ""
  for n in range(N):
    if (num >> (N-1-n) & 1):
      tmpl_1 += S_l[n]
      tmpr_1 += S_r[n]
    else:
      tmpl_2 += S_l[n]
      tmpr_2 += S_r[n]
  dict_l[tmpl_1+"_"+tmpl_2] = dict_l.get(tmpl_1+"_"+tmpl_2, 0) + 1
  dict_r[tmpr_1+"_"+tmpr_2] = dict_r.get(tmpr_1+"_"+tmpr_2, 0) + 1
for k, v in dict_l.items():
  ans += v*dict_r.get(k,0)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = list(input())
left=s[:n]
right=s[n:]
right.reverse()

from itertools import *
from collections import defaultdict
d = defaultdict(int)

for pro in product([0,1], repeat=n):
    s1=s2=""
    for i,p in enumerate(pro):
        if p==0:
            s1+=left[i]
        else:
            s2+=left[i]
    d[(s1,s2)]+=1

ans=0
for pro in product([0,1], repeat=n):
    s1=s2=""
    for i,p in enumerate(pro):
        if p==0:
            s1+=right[i]
        else:
            s2+=right[i]
    ans+=d[(s1,s2)]
print(ans)

Submission status: Accepted

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

Solution code:
N = int(input())
S = input()
S1 = S[:N]
S2 = S[N:][::-1]
from itertools import groupby, accumulate, product, permutations, combinations
from collections import defaultdict
def half(S):
  dic = defaultdict(lambda: 0)
  for pro in product([0,1],repeat=N):
    s1 = s2 = ''
    for i,p in enumerate(pro):
      s1 += S[i]*p
      s2 += S[i]*(1-p)
    dic[(s1,s2)] += 1
  return dic
dic1 = half(S1)
dic2 = half(S2)
ans = 0
for k,v in dic1.items():
  ans += v*dic2[k]
print(ans)

Submission status: Accepted

Solution code:
def main(n,a):
    a1,a2=a[:n],a[n:]
    a2.reverse()
    d1={}
    d2={}
    for i in range(2**n):
        r1=[]
        r2=[]
        l1=[]
        l2=[]
        for j in range(n):
            if (i>>j)&1:
                r1.append(a1[j])
                r2.append(a2[j])
            else:
                l1.append(a1[j])
                l2.append(a2[j])
        s1=''.join(r1)+'-'+''.join(l1)
        s2=''.join(r2)+'-'+''.join(l2)
        if s1 in d1:d1[s1]+=1
        else:d1[s1]=1
        if s2 in d2:d2[s2]+=1
        else:d2[s2]=1
    ans=0
    for k in d1:
        if k in d2:
            ans+=d1[k]*d2[k]
    return ans

n=int(input())
a=list(input())
#a=list(map(int,input().split()))
#b=list(map(int,input().split()))
#ab=[list(map(int,input().split())) for _ in range(n)]
print(main(n,a))

Submission status: Accepted

Solution code:
def f(i, k):
    if i == n and k == 0:
        global d
        hr1, hb1 = 0, 0
        hr2, hb2 = 0, 0
        cntr, cntb = 0, 0
        for j in range(n):
            if c[j]:
                hr1 += x[j] * powb1[cntr]
                hr2 += x[j] * powb2[cntr]
                hr1 %= mod
                hr2 %= mod
                cntr += 1
            else:
                hb1 += x[j] * powb1[cntb]
                hb2 += x[j] * powb2[cntb]
                hb1 %= mod
                hb2 %= mod
                cntb += 1
        if min(cntr, cntb) == 0:
            return
        if (hr1, hr2, hb1, hb2) in d:
            d[(hr1, hr2, hb1, hb2)] += 1
        else:
            d[(hr1, hr2, hb1, hb2)] = 1
        return
    elif i == n and k == 1:
        hr1, hb1 = 0, 0
        hr2, hb2 = 0, 0
        cntr, cntb = 0, 0
        for j in range(n):
            if c[j]:
                hr1 += y[j] * powb1[cntr]
                hr2 += y[j] * powb2[cntr]
                hr1 %= mod
                hr2 %= mod
                cntr += 1
            else:
                hb1 += y[j] * powb1[cntb]
                hb2 += y[j] * powb2[cntb]
                hb1 %= mod
                hb2 %= mod
                cntb += 1
        if min(cntr, cntb) == 0:
            return
        if (hr1, hr2, hb1, hb2) in d:
            global ans
            ans += d[(hr1, hr2, hb1, hb2)]
        return
    c[i] = 1
    f(i + 1, k)
    c[i] = 0
    f(i + 1, k)


n = int(input())
s = list(input())
mod = pow(2, 31) - 1
b1, b2 = 27, 31
powb1 = [pow(27, i, mod) for i in range(n)]
powb2 = [pow(31, i, mod) for i in range(n)]
d = {}
x, y = [], []
for i in range(n):
    x.append(ord(s[i]) - 96)
    y.append(ord(s[-(i + 1)]) - 96)
ans = 0 if not x == y else 2
c = [0] * n
f(0, 0)
c = [0] * n
f(0, 1)
print(ans)

Submission status: Accepted

Solution code:
def f(i, k):
    if i == n and k == 0:
        global d
        hr1, hb1 = 0, 0
        hr2, hb2 = 0, 0
        cntr, cntb = 0, 0
        for j in range(n):
            if c[j]:
                hr1 += x[j] * pow(b1, cntr, mod)
                hr2 += x[j] * pow(b2, cntr, mod)
                hr1 %= mod
                hr2 %= mod
                cntr += 1
            else:
                hb1 += x[j] * pow(b1, cntb, mod)
                hb2 += x[j] * pow(b2, cntb, mod)
                hb1 %= mod
                hb2 %= mod
                cntb += 1
        if min(cntr, cntb) == 0:
            return
        if (hr1, hr2, hb1, hb2) in d:
            d[(hr1, hr2, hb1, hb2)] += 1
        else:
            d[(hr1, hr2, hb1, hb2)] = 1
        return
    elif i == n and k == 1:
        hr1, hb1 = 0, 0
        hr2, hb2 = 0, 0
        cntr, cntb = 0, 0
        for j in range(n):
            if c[j]:
                hr1 += y[j] * powb1[cntr]
                hr2 += y[j] * powb2[cntr]
                hr1 %= mod
                hr2 %= mod
                cntr += 1
            else:
                hb1 += y[j] * powb1[cntb]
                hb2 += y[j] * powb2[cntb]
                hb1 %= mod
                hb2 %= mod
                cntb += 1
        if min(cntr, cntb) == 0:
            return
        if (hr1, hr2, hb1, hb2) in d:
            global ans
            ans += d[(hr1, hr2, hb1, hb2)]
        return
    c[i] = 1
    f(i + 1, k)
    c[i] = 0
    f(i + 1, k)


n = int(input())
s = list(input())
mod = pow(2, 31) - 1
b1, b2 = 27, 31
powb1 = [pow(27, i, mod) for i in range(n)]
powb2 = [pow(31, i, mod) for i in range(n)]
d = {}
x, y = [], []
for i in range(n):
    x.append(ord(s[i]) - 96)
    y.append(ord(s[-(i + 1)]) - 96)
ans = 0 if not x == y else 2
c = [0] * n
f(0, 0)
c = [0] * n
f(0, 1)
print(ans)

Submission status: Accepted

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(red) + '+' + ''.join(blue)
    if key in hash_S1:
        hash_S1[key] += 1
    else:
        hash_S1[key] = 1

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

Solution code:
from itertools import product
from collections import defaultdict

def solve(S):
    def helper(s):
        n = len(s)
        d = defaultdict(int)
        for p in product((True,False),repeat=n):
            t = [-1]*(n+1)
            t[-1] = sum(p)
            i = 0
            j = n-1
            for c,f in zip(s,p):
                if f:
                    t[i] = c
                    i += 1
                else:
                    t[j] = c
                    j -= 1
            d[tuple(t)] += 1
        return d

    S = [ord(c)-ord('a') for c in S]
    n = len(S)//2
    d1 = helper(S[:n])
    d2 = helper(S[:n-1:-1])
    res = 0
    for k,c in d1.items():
        res += c*d2[k]

    return res


if __name__ == '__main__':
    N = int(input())
    S = input()
    print(solve(S))

Submission status: Accepted

Solution code:
from collections import defaultdict

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


def solve(s):
    d = defaultdict(int)
    for i in range(2**n):
        blue = red = ""
        for k in range(n):
            if 1 << k & i:
                blue += s[k]
            else:
                red += s[k]
        d[(blue, red)] += 1
    return d


left = solve(s[:n])
right = solve(s[::-1][:n])


ans = 0
for (b, r), v in left.items():
    ans += v * right[(r, b)]

print(ans)

Submission status: Accepted

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

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

for bit in range(1 << n):
    x = ""
    y = ""
    z = ""
    w = ""
    for i in range(n):
        if bit >> i & 1:
            x += a[i]
            z += b[i]
        else:
            y += a[i]
            w += b[i]
    d[x+'ω'+y] += 1
    e[z+'ω'+w] += 1

print(sum([e[k] * v for k, v in d.items()]))

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N = I()
S = LS2()

from collections import defaultdict

d_left = defaultdict(int)
d_right = defaultdict(int)

# 半分全列挙

for i in range(2**N):
    left_red = ''
    left_blue = ''
    right_red = ''
    right_blue = ''
    for j in range(N):
        if (i >> j) & 1:
            left_red += S[j]
        else:
            left_blue += S[j]
    for j in range(2*N-1,N-1,-1):
        if (i >> (j-N)) & 1:
            right_red += S[j]
        else:
            right_blue += S[j]
    d_left[(left_red,left_blue)] += 1
    d_right[(right_red,right_blue)] += 1

ans = 0
for key in d_left.keys():
    ans += d_left[key]*d_right[key]

print(ans)

Submission status: Accepted

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

a = s[:n]
b = s[n:][::-1]
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: Accepted

Solution code:
ans=0

from collections import defaultdict
n=int(input())
s=input()
a=s[:n]
b=s[n:][::-1]
def coloring(x):
    N=1<<n
    dc=defaultdict(int)
    for i in range(N):
        r=''
        b=''
        for j in range(n):
            if i>>j&1:
                r+=x[j]
            else:
                b+=x[j]
        dc[r+'-'+b]+=1
    return dc    

fd=coloring(a)
ld=coloring(b)

for i,j in fd.items():
    ans+=ld[i]*j

print(ans)

Submission status: Accepted

Solution code:
from itertools import product
from collections import defaultdict
N = int(input())
S = input()

ans = 0
D = defaultdict(int)
for pattern in product([0, 1], repeat=N):
    red = ''.join([s for s, p in zip(S[:N], pattern) if p == 0])
    blue = ''.join([s for s, p in zip(S[:N], pattern) if p == 1])
    D[(red, blue)] += 1

for pattern in product([0, 1], repeat=N):
    red = ''.join([s for s, p in zip(S[N:], pattern) if p == 0])
    blue = ''.join([s for s, p in zip(S[N:], pattern) if p == 1])
    ans += D[(blue[::-1], red[::-1])]
print(ans)

Submission status: Accepted

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():
    ans += v1 * ctr2[(r1,b1)]
print(ans)

Submission status: Accepted

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def NLI(n):return [[int(i) for i in input().split()] for i in range(n)]
def NLI_(n):return [[int(i)-1 for i in input().split()] for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def RLI(n=8,a=1,b=10):return [random.randint(a,b)for i in range(n)]
def RI(a=1,b=10):return random.randint(a,b)
def Rtest(T):
    case,err=0,0
    for i in range(T):
        inp=INP()
        a1,ls=naive(*inp)
        a2=solve(*inp)
        if a1!=a2:
            print((a1,a2),inp)
            err+=1
        case+=1
    print('Tested',case,'case with',err,'errors')
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
#mo=998244353
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**9)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()


show_flg=False
show_flg=True

ans=0

n=I()
s=input()
a=s[:n]
b=s[n:][::-1]

def coloring(x):
    N=1<<n
    dc=defaultdict(int)
    for i in range(N):
        r=''
        b=''
        for j in range(n):
            if i>>j&1:
                r+=x[j]
            else:
                b+=x[j]
        dc[r+'-'+b]+=1
    return dc    

fd=coloring(a)
ld=coloring(b)

for i,j in fd.items():
    ans+=ld[i]*j

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N = I()
S = LS2()

from collections import defaultdict

d_left = defaultdict(int)
d_right = defaultdict(int)

for i in range(2**N):
    left_red = ''
    left_blue = ''
    right_red = ''
    right_blue = ''
    for j in range(N):
        if (i >> j) & 1:
            left_red += S[j]
        else:
            left_blue += S[j]
    for j in range(2*N-1,N-1,-1):
        if (i >> (j-N)) & 1:
            right_red += S[j]
        else:
            right_blue += S[j]
    d_left[(left_red,left_blue)] += 1
    d_right[(right_red,right_blue)] += 1

ans = 0
for key in d_left.keys():
    ans += d_left[key]*d_right[key]

print(ans)

Submission status: Accepted

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

n = int(input())
S = input().rstrip()
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: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict
from itertools import compress 
N = int(input())
S = input().strip()
#N = 18
#S = 'abc' * 12
S1 = S[:N]
S2 = S[N:][::-1]

Ls = 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 = ""
    B = ""
    for s,b in zip(S1,bs):
        if b == 1:
            R += s
        else:
            B += s
    Ls[n][(R,B[::-1])] += 1

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

print(ans)