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

s1 = []
dic_s2 = defaultdict(int)

for x in product([0, 1], repeat=N):
	s1_red = ""
	s1_blue = ""
	s2_red = ""
	s2_blue = ""
	for i in range(N):
		if x[i]:
			s1_red += S[i]
			s2_red += S[N+i]
		else:
			s1_blue += S[i]
			s2_blue += S[N+i]

	s1.append((s1_red, s1_blue))
	dic_s2[(s2_blue[::-1], s2_red[::-1])] += 1

ans = 0
for x in s1:
	ans += dic_s2[x]

print(ans)

Submission status: Accepted

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


def main():
	N = INT()
	S = input()

	s1 = []
	dic_s2 = defaultdict(int)

	for x in product([0, 1], repeat=N):
		s1_red = ""
		s1_blue = ""
		s2_red = ""
		s2_blue = ""
		for i in range(N):
			if x[i]:
				s1_red += S[i]
				s2_red += S[N+i]
			else:
				s1_blue += S[i]
				s2_blue += S[N+i]

		s1.append((s1_red, s1_blue))
		dic_s2[(s2_blue[::-1], s2_red[::-1])] += 1

	ans = 0
	for x in s1:
		ans += dic_s2[x]

	print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

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

def main():

	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:
		ans += dic_f[key] * dic_l[key]

	print(ans)


if __name__ == '__main__':
	main()

Submission status: Accepted

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:
	ans += dic_f[key] * dic_l[key]

print(ans)

Submission status: Accepted

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

def main():

	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:
		ans += dic_f[key] * dic_l[key]

	print(ans)


if __name__ == '__main__':
	main()

Submission status: Accepted

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

s1 = []
dic_s2 = defaultdict(int)

for x in product([0, 1], repeat=N):
	s1_red = ""
	s1_blue = ""
	s2_red = ""
	s2_blue = ""
	for i in range(N):
		if x[i]:
			s1_red += S[i]
			s2_red += S[N+i]
		else:
			s1_blue += S[i]
			s2_blue += S[N+i]

	s1.append((s1_red, s1_blue))
	dic_s2[(s2_blue[::-1], s2_red[::-1])] += 1

ans = 0
for x in s1:
	ans += dic_s2[x]

print(ans)

Submission status: Accepted

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

l = Counter()
for i in range(2 ** n):
    r, b = [], []
    for j in range(n):
        if (i >> j) & 1:
            r.append(s[j])
        else:
            b.append(s[j])
    r = ''.join(r)
    b = ''.join(b)
    l[(r[::-1], b[::-1])] += 1

ans = 0
for i in range(2 ** n):
    r, b = [], []
    for j in range(n):
        if (i >> j) & 1:
            r.append(s[n + j])
        else:
            b.append(s[n + j])
    
    r = ''.join(r)
    b = ''.join(b)
    ans += l[(b, r)]

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

n = inn()
s = ins()
l = s[:n]
r = s[n:]
r = r[::-1]
h = defaultdict(int)
for i in range(2**n):
    x = ""
    y = ""
    for j in range(n):
        if (i>>j)%2==0:
            x += l[j]
        else:
            y += l[j]
    h[(x,y)] += 1
ans = 0
for i in range(2**n):
    x = ""
    y = ""
    for j in range(n):
        if (i>>j)%2==0:
            x += r[j]
        else:
            y += r[j]
    if (x,y) in h:
        #ddprint(f"{x=} {y=} h {h[(x,y)]}")
        ans += h[(x,y)]
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)
import math
import itertools
INF = float('inf')
from heapq import heapify, heappop, heappush

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

    l_dict = {}
    r_dict = {}
    L = S[:n]
    R = S[n:]
    for i in range(2**n):
        lr, lb, rr, rb = '', '', '', ''
        for j in range(n):
            if (i>>j) & 1:
                lr += L[j]
                rr += R[j]
            else:
                lb += L[j]
                rb += R[j]
        rr = rr[::-1]
        rb = rb[::-1]

        if l_dict.get((lr,lb)):
            l_dict[(lr,lb)] += 1
        else:
            l_dict[(lr,lb)] = 1
        if r_dict.get((rb,rr)):
            r_dict[(rb,rr)] += 1
        else:
            r_dict[(rb,rr)] = 1
    ans = 0
    for k, v in l_dict.items():
        if k in r_dict:
            ans += v*r_dict[k]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
S = input()
S = S[:N] + S[N:][::-1]

import collections

def count(S):
    n = len(S)
    T = []
    for i in range(2**n):
        r, b = '', ''
        for j in range(n):
            if i >> j & 1:
                r += S[j]
            else:
                b += S[j]
        T.append((r, b))
    return collections.Counter(T)

A = count(S[:N])    
B = count(S[N:])

ans  = 0
for a in A:
    if a in B:
        ans += A[a]*B[a]

print(ans)

Submission status: Accepted

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

    L = s[:n]
    R = s[n:]
    R.reverse()

    br_l = defaultdict(int)
    br_r = defaultdict(int)

    L_map = dict()

    for i in range(2**n):
        al,bl,ar,br = '','','',''
        for j in range(n):
            if (i>>j)%2:
                al += L[j]
                ar += R[j]
            else:
                bl += L[j]
                br += R[j]
        br_l[(al,bl)] += 1
        br_r[(ar,br)] += 1

    ans = 0
    for k in br_l.keys():
        ans+= br_r[k] * br_l[k]
    print(ans)

main()

Submission status: Accepted

Solution code:
from collections import defaultdict
n=int(input())
s=list(input())
left=s[:n]
right=list(reversed(s[n:]))

DL=defaultdict(int)
for i in range(2**n):
    red=[]
    blue=[]
    for j in range(n):
        if (i>>j)&1:
            red.append(left[j])
        else:
            blue.append(left[j])
    DL["".join(red),"".join(blue)]+=1

DR=defaultdict(int)
for i in range(2**n):
    red=[]
    blue=[]
    for j in range(n):
        if (i>>j)&1:
            red.append(right[j])
        else:
            blue.append(right[j])
    DR["".join(blue),"".join(red)]+=1

ans=0
for k,v in DL.items():
    if k in DR:
        ans+=v*DR[k]
print(ans)

Submission status: Accepted

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    s = input()
    ld = defaultdict(int)
    rd = defaultdict(int)

    for i in range(2**n):
        r = ""
        b = ""
        for j,sj in enumerate(s[:n:]):
            if (i>>j)&1:
                r += sj
            else:
                b += sj
        ld[(r,b)] += 1

    for i in range(2**n):
        r = ""
        b = ""
        for j,sj in enumerate(s[2*n-1:n-1:-1]):
            if (i>>j)&1:
                r += sj
            else:
                b += sj
        rd[(r,b)] += 1

    ans = 0
    for lk,lv in ld.items():
        ans += lv*rd[lk]
    print(ans)
    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

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

d = defaultdict(int)

s1 = s[:n]
s2 = s[n:][::-1]

for i in range(2**n):
    left,right = [],[]
    for j in range(n):
        if(i >> j)&1:
            left.append(s1[j])
        else:
            right.append(s1[j])
    d[ ''.join(left) + '_' + ''.join(right) ] += 1

ans = 0
for i in range(2**n):
    left,right = [],[]
    for j in range(n):
        if(i >> j)&1:
            left.append(s2[j])
        else:
            right.append(s2[j])
    ans += d[ ''.join(left) + '_' + ''.join(right) ]

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, cos, radians, pi, sin
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n = I()
s = S()
s1 = s[:n]
s2 = s[n:][::-1]
D1 = defaultdict(int)
D2 = defaultdict(int)
for i in range(2 ** n):
    a1 = ""
    b1 = ""
    for j in range(n):
        if i >> j & 1:
            a1 += s1[j]
        else:
            b1 += s1[j]
    D1[(a1, b1)] += 1

for i in range(2 ** n):
    a2 = ""
    b2 = ""
    for j in range(n):
        if i >> j & 1:
            a2 += s2[j]
        else:
            b2 += s2[j]
    D2[(a2, b2)] += 1

ret = 0
for i in D1:
    ret += D1[i] * D2[i]

print(ret)

Submission status: Accepted

Solution code:
N=int(input())
S=input()
S,T=S[:N],S[N:][::-1]
A=dict()
B=dict()
X1,Y1,X2,Y2,Z=0,0,0,0,0
for i in range(1<<N):
  X1,Y1,X2,Y2,Z='','','','',1
  for j in range(N):
    if i&Z:
      X1+=S[j]
      X2+=T[j]
    else:
      Y1+=S[j]
      Y2+=T[j]
    Z<<=1
  A[(X1,Y1)]=A.get((X1,Y1),0)+1
  B[(X2,Y2)]=B.get((X2,Y2),0)+1
P=0
Z=list(A.keys())
for i in range(len(Z)):
  P+=A[Z[i]]*B.get(Z[i],0)
print(P)

Submission status: Accepted

Solution code:
def f():
    n,s=int(input()),input()
    a,b=s[n-1::-1],s[n:]
    ad={}
    bd={}
    for i in range(2**n):
        sa,ta,sb,tb="","","",""
        for j in range(n):
            if i%2:
                sa+=a[j]
                sb+=b[j]
            else:
                ta+=a[j]
                tb+=b[j]
            i//=2
        ad[(sa,ta)]=(1 if (sa,ta)not in ad else ad[(sa,ta)]+1)
        bd[(sb,tb)]=(1 if (sb,tb)not in bd else bd[(sb,tb)]+1) 
    ans=0
    for k in ad:
        if k in bd:ans+=bd[k]*ad[k]
    print(ans)
if __name__ == "__main__":
    f()

Submission status: Accepted

Solution code:
def f():
    n,s=int(input()),input()
    a,b=s[n-1::-1],s[n:]
    from collections import defaultdict
    ad=defaultdict(int)
    bd=defaultdict(int)
    for i in range(2**n):
        sa,ta,sb,tb="","","",""
        for j in range(n):
            if i%2:
                sa+=a[j]
                sb+=b[j]
            else:
                ta+=a[j]
                tb+=b[j]
            i//=2
        ad[(sa,ta)]+=1
        bd[(sb,tb)]+=1
    ans=0
    for k in ad:
        ans+=bd[k]*ad[k]
    print(ans)
if __name__ == "__main__":
    f()

Submission status: Accepted

Solution code:
def t():
    n=int(input())
    s=input()
    from collections import defaultdict
    l,r=s[:n],s[-1:-n-1:-1]
    d=defaultdict(int)
    for i in range(2**n):
        a={j for j in range(n)if (i>>j)%2}
        d[("".join(l[p] for p in sorted(list(a))),"".join(l[o] for o in range(n)if o not in a))]+=1
    ans=0
    for i in range(2**n):
        a={j for j in range(n)if (i>>j)%2}
        ans+=d[("".join(r[p] for p in sorted(list(a))),"".join(r[o] for o in range(n)if o not in a))]

    print(ans)
if __name__ == "__main__":
    t()

Submission status: Accepted

Solution code:
n=int(input())
s=input()
from collections import defaultdict
l,r=s[:n],s[-1:-n-1:-1]
d=defaultdict(int)
for i in range(2**n):
    a={j for j in range(n)if (i>>j)%2}
    d[("".join(l[p] for p in sorted(list(a))),"".join(l[o] for o in range(n)if o not in a))]+=1
ans=0
for i in range(2**n):
    a={j for j in range(n)if (i>>j)%2}
    ans+=d[("".join(r[p] for p in sorted(list(a))),"".join(r[o] for o in range(n)if o not in a))]

print(ans)

Submission status: Accepted

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

L = s[0:n]
R = s[n:]
R = list(R)
R.reverse()
R = ''.join(R)

DL = {}
for i in range(2**n):
    p = ''
    q = ''
    for j in range(n):
        if (i >> j)&1:
            p += L[j]
        else:
            q += L[j]
    if (p, q) in DL:
        DL[(p, q)] += 1
    else:
        DL[(p, q)] = 1

DR = {}
for i in range(2**n):
    p = ''
    q = ''
    for j in range(n):
        if (i >> j)&1:
            p += R[j]
        else:
            q += R[j]
    if (p, q) in DR:
        DR[(p, q)] += 1
    else:
        DR[(p, q)] = 1

#print(DL)
#print(DR)
ans = 0
for k, v in DL.items():
    if k in DR:
        ans += v*DR[k]
print(ans)

Submission status: Accepted

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

N = int(input())
s = input()[:-1]
cnt = defaultdict(int)

for S in range(1<<N):
    red, blue = [], []
    
    for i in range(N):
        if (S>>i)&1:
            red.append(s[i])
        else:
            blue.append(s[i])
    
    cnt[(''.join(red), ''.join(blue))] += 1

s = s[::-1]
ans = 0

for S in range(1<<N):
    red, blue = [], []
    
    for i in range(N):
        if (S>>i)&1:
            red.append(s[i])
        else:
            blue.append(s[i])
    
    ans += cnt[(''.join(blue), ''.join(red))]

print(ans)

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

# 左N個のマスをどう塗るかで半分全列挙

ans = 0
left = []
right = []
for i in range(2**N):
    red = []
    blue = []
    for j in range(N):
        if (i >> j) & 1:
            red.append(S[j])
        else:
            blue.append(S[j])
    red = ''.join(red)
    blue = ''.join(blue)
    left.append((red,blue))
for i in range(2**N):
    red = []
    blue = []
    for j in range(N):
        if (i >> j) & 1:
            red.append(S[j+N])
        else:
            blue.append(S[j+N])
    red,blue = blue,red
    red.reverse()
    blue.reverse()
    red = ''.join(red)
    blue = ''.join(blue)
    right.append((red,blue))

from operator import itemgetter

right = sorted(right,key = itemgetter(0,1))

from bisect import bisect_left,bisect

ans = 0
for i in range(2**N):
    ans += bisect(right,left[i]) - bisect_left(right,left[i])

print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
s = input()
t = s[-1:-n-1:-1]
def sub(r,b):
    # tを分割してr,bを作る通り数
    dp = [[0]*(len(b)+1) for _ in range(len(r)+1)]
    dp[0][0] = 1
    for i in range(len(r)+1):
        for j in range(len(b)+1):
#             if i+j>=n:
#                 continue
            if i<len(r) and t[i+j]==r[i]:
                dp[i+1][j] += dp[i][j]
            if j<len(b) and t[i+j]==b[j]:
                dp[i][j+1] += dp[i][j]
    return dp[len(r)][len(b)]


ans = 0
for bit in range(1<<n):
    r = []
    b = []
    for i in range(n):
        if bit>>i&1:
            r.append(s[i])
        else:
            b.append(s[i])
    ans += sub(r,b)
print(ans)

Submission status: Accepted

Solution code:
def f():
    n=int(input())
    s=list(input())
    a,b=s[n-1::-1],s[n:]
    from collections import defaultdict

    ad=defaultdict(int)
    bd=defaultdict(int)
    for i in range(2**n):
        sa,ta,sb,tb="","","",""
        for j in range(n):
            if i%2:
                sa+=a[j]
                sb+=b[j]
            else:
                ta+=a[j]
                tb+=b[j]
            i//=2
        ad[(sa,ta)]+=1
        bd[(sb,tb)]+=1
    ans=0
    for k in ad:
        if k in bd:
            ans+=bd[k]*ad[k]
    print(ans)
if __name__ == "__main__":
    f()

Submission status: Accepted

Solution code:
N = int(input())
S = input()
first = S[:N]
latter = S[N:][::-1]

dic = {}
digit = "0"+str(N)+"b"
for i in range(2**N):
    pattern = list(format(i,digit))
    red = []
    blue = []
    for j in range(N):
        if pattern[j] == "1":
            red.append(first[j])
        else:
            blue.append(first[j])
    key = ",".join(("".join(red),"".join(blue)))
    if key in dic:
        dic[key] += 1
    else:
        dic[key] = 1

ans = 0
for i in range(2**N):
    pattern = list(format(i,digit))
    red = []
    blue = []
    for j in range(N):
        if pattern[j] == "1":
            red.append(latter[j])
        else:
            blue.append(latter[j])
    key = ",".join(("".join(red),"".join(blue)))
    if key in dic:
        ans += dic[key]

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
N = int(input())
S = list(input())
L = S[:N]
R = S[:2*N][::-1]


digit = "0"+str(N)+"b"
LDic={}
for i in range(2**N):
    pattern = format(i,digit)
    red = []
    blue = []
    for i in range(N):
        if pattern[i] == "1":
            red.append(L[i])
        else:
            blue.append(L[i])
    red = "".join(red)
    blue = "".join(blue)
    key = ",".join([red,blue])
    if key in LDic:
        LDic[key] += 1
    else:
        LDic[key] = 1

RDic={}
for i in range(2**N):
    pattern = format(i,digit)
    red = []
    blue = []
    for i in range(N):
        if pattern[i] == "1":
            red.append(R[i])
        else:
            blue.append(R[i])
    red = "".join(red)
    blue = "".join(blue)
    key = ",".join([blue,red])
    if key in RDic:
        RDic[key] += 1
    else:
        RDic[key] = 1
ans = 0
for k,v in LDic.items():
    if k in RDic:
        ans += v*RDic[k]
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def S(): return input()
# ----------------------------------------------------------- #

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:
        ans += A[key]*B[key]

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def S(): return input()
# ----------------------------------------------------------- #

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:
        ans += A[key]*B[key]

print(ans)

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/agc026/submissions/10971924を参考にした

from collections import defaultdict
n = int(input())
s = input()
ls = s[:n:]
rs = s[:n-1:-1]
d = defaultdict(int)

def full_research(sa,r,b,t):
    if t == n:
        d[(r,b)] += 1
        return
    full_research(sa,r+sa[t],b,t+1)
    full_research(sa,r,b+sa[t],t+1)

full_research(ls,"","",0)
dl = d
d = defaultdict(int)
full_research(rs,"","",0)

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

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from collections import defaultdict

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 左右で分けてそれぞれ全探索
N = ir()
S = sr()
answer = 0
latter = S[N:][::-1]

dic_left = defaultdict(int)
for pattern in range(1<<N):
    red = ''; blue = ''
    for i in range(N):
        if pattern>>i & 1:
            red += S[i]
        else:
            blue += S[i]
    key = (red, blue)
    if key in dic_left:
        dic_left[key] += 1
    else:
        dic_left[key] = 1

dic_right = defaultdict(int)
for pattern in range(1<<N):
    red = ''; blue = ''
    for i in range(N):
        if pattern>>i & 1:
            red += latter[i]
        else:
            blue += latter[i]
    key = (red, blue)
    if key in dic_right:
        dic_right[key] += 1
    else:
        dic_right[key] = 1

answer = 0
for k, v in dic_left.items():
    if k in dic_right:
        answer += v * dic_right[k]

print(answer)
# 解説

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from collections import defaultdict

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 左右で分けてそれぞれ全探索
N = ir()
S = sr()
answer = 0
latter = S[N:][::-1]

dic_left = defaultdict(int)
for pattern in range(1<<N):
    red = ''; blue = ''
    for i in range(N):
        if pattern>>i & 1:
            red += S[i]
        else:
            blue += S[i]
    key = (red, blue)
    dic_left[key] += 1

dic_right = defaultdict(int)
for pattern in range(1<<N):
    red = ''; blue = ''
    for i in range(N):
        if pattern>>i & 1:
            red += latter[i]
        else:
            blue += latter[i]
    key = (red, blue)
    dic_right[key] += 1

answer = 0
for k, v in dic_left.items():
    if k in dic_right:
        answer += v * dic_right[k]

print(answer)
# 解説

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from collections import defaultdict

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 一番左を赤として2倍、Counter、N文字ずつ選ぶ
# 制約が少ないので全探索も可能
N = ir()
S = sr()
answer = 0
former = S[:N]
latter = S[N:][::-1]

dic_left = defaultdict(int)
for pattern in range(1<<N):
    red = ''; blue = ''
    for i in range(N):
        if pattern>>i & 1:
            red += S[i]
        else:
            blue += S[i]
    key = (red, blue)
    if key in dic_left:
        dic_left[key] += 1
    else:
        dic_left[key] = 1

dic_right = defaultdict(int)
for pattern in range(1<<N):
    red = ''; blue = ''
    for i in range(N):
        if pattern>>i & 1:
            red += latter[i]
        else:
            blue += latter[i]
    key = (red, blue)
    if key in dic_right:
        dic_right[key] += 1
    else:
        dic_right[key] = 1

answer = 0
for k, v in dic_left.items():
    if k in dic_right:
        answer += v * dic_right[k]

print(answer)
# 解説