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:
from collections import defaultdict
import sys
input = sys.stdin.readline

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

cnt = defaultdict(int)
for bit in range(1 << N):
    a = b = ''
    for i in range(N):
        if bit >> i & 1:
            a += S[i]
        else:
            b += S[i]
    cnt[(a, b)] += 1
ans = 0
for bit in range(1 << N):
    a = b = ''
    for i in range(N):
        if bit >> i & 1:
            a += S[N+i]
        else:
            b += S[N+i]
    ans += cnt[(b[::-1], a[::-1])]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N = int(rl())
    S = rl().rstrip()
    s1, s2 = S[:N], S[N:][::-1]
    
    l_dict = defaultdict(int)
    r_dict = defaultdict(int)
    for i in range(N + 1):
        for red_idx in combinations(range(N), i):
            red, blue = '', ''
            for j in range(N):
                if j in red_idx:
                    red += s1[j]
                else:
                    blue += s1[j]
            l_dict[red + ' ' + blue] += 1
    for i in range(N + 1):
        for red_idx in combinations(range(N), i):
            red, blue = '', ''
            for j in range(N):
                if j in red_idx:
                    red += s2[j]
                else:
                    blue += s2[j]
            r_dict[red + ' ' + blue] += 1
    
    ans = sum(l_dict[key] * r_dict[key] for key in l_dict)
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

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

#処理内容
def main():
	N = int(input())
	S = input()
	D1 = defaultdict(int)
	D2 = defaultdict(int)
	for i in range(1 << N):
		R = ""
		B = ""
		for j in range(N):
			if ((i >> j) & 1) == 1:
				R += S[j]
			else:
				B += S[j]

		RB = R + "," + B
		D1[RB] += 1

	for i in range(1 << N):
		R = ""
		B = ""
		for j in range(N):
			if ((i >> j) & 1) == 1:
				R += S[-1 - j]
			else:
				B += S[-1 - j]

		RB = R + "," + B
		D2[RB] += 1

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

	print(ans)


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import itertools

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

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

dicleft = {}
for v in itertools.product([0, 1], repeat=n):
    red, blue = '', ''
    for i in range(n):
        if v[i] == 0: red += left[i]
        else: blue += left[i]
    idx = red + '_' + blue
    if idx in dicleft:
        dicleft[idx] += 1
    else:
        dicleft[idx] = 1

dicright = {}
for v in itertools.product([0, 1], repeat=n):
    red, blue = '', ''
    for i in range(n):
        if v[i] == 0: red += right[i]
        else: blue += right[i]
    idx = red + '_' + blue
    if idx in dicright:
        dicright[idx] += 1
    else:
        dicright[idx] = 1

ans = 0
for key, value in dicleft.items():
    if key in dicright:
        ans += value * dicright[key]
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
S = input()
SL = S[:N]
SR = S[N:][::-1]

ans = 0
memo = defaultdict(int)

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

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

print(ans)

Submission status: Accepted

Solution code:
from collections import *

N = int(input())
s = list(input())
cnt = defaultdict(lambda : defaultdict(int))

for S in range(2**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.reverse()
ans = 0

for S in range(2**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:
n=int(input())
s=input()
#半分全列挙+bit全探索だ！！！！！！天才！！！！！！！！！
left={}
right={}
sl=s[:n]
sr=s[n:]
for i in range(1<<(n)):
  lr=lb=""
  rr=rb=""
  for j in range(n):
    if i&(1<<j):
      lr+=sl[j]
      rr+=sr[j]
    else:
      lb+=sl[j]
      rb+=sr[j]
  l=lr+","+lb
  r=(rr+","+rb)[::-1]
  if l in left:left[l]+=1
  else:left[l]=1
  if r in right:right[r]+=1
  else:right[r]=1
ans=0
for i in left:
  if i in right:ans+=left[i]*right[i]
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
S = input()
S_former = S[:N]
S_latter = S[N:][::-1]
ans = 0


def analyzer(St):
    n = len(St)
    A = []
    for i in range(2**n):
        red = ''
        blue = ''
        for j in range(n):
            if (i >> j) & 1 == 1:
                red += St[j]
            else:
                blue += St[j]
        A.append((red, blue))
    return Counter(A)


SC_former = analyzer(S_former)
SC_latter = analyzer(S_latter)
for ke, va in SC_former.items():
    ans += SC_latter[ke] * va

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

def get_s(s, i):
  s1 = s2 = ''
  for j in range(N):
    if i>>j & 1:
      s1 += s[j]
    else:
      s2 += s[j]
  return (s1, s2)

d1 = defaultdict(int)
d2 = defaultdict(int)
for i in range(2**N):
  s1 = get_s(S1, i)
  d1[s1] += 1
  s2 = get_s(S2, i)
  d2[s2] += 1

ans = 0
for k in d1:
  ans += d1[k] * d2[k]

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=list(input())
l=[s[i] for i in range(n)]
r=[s[i] for i in range(n,2*n)]
r=r[::-1]
from collections import defaultdict
ld=defaultdict(int)
rd=defaultdict(int)
for i in range(2**n):
    ls=['', '']
    rs=['', '']
    for j in range(n):
        if (i>>j)%2==0:
            ls[0]+=l[j]
            rs[0]+=r[j]
        elif (i>>j)%2==1:
            ls[1]+=l[j]
            rs[1]+=r[j]
    ls=tuple(ls)
    rs=tuple(rs)
    ld[ls]+=1
    rd[rs]+=1

cnt=0
for k in ld.keys():
    a=ld[k]
    b=rd[k]
    cnt+=a*b
print(cnt)

Submission status: Accepted

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

first={}
last={}

def dfs(r,b,num):
    if num==N:
        if (r,b) not in first:
            first[(r,b)]=0
        first[(r,b)]+=1
        return 0

    if len(r)<N:
        dfs(r+S[num],b,num+1)

    if len(b)<N:
        dfs(r,S[num]+b,num+1)

dfs("","",0)

def dfs2(r,b,num):
    if num==2*N:
        if (r,b) not in last:
            last[(r,b)]=0
        last[(r,b)]+=1
        return 0

    if len(r)<N:
        dfs2(r+S[num],b,num+1)

    if len(b)<N:
        dfs2(r,S[num]+b,num+1)

dfs2("","",N)

for r,b in first:
    if (b,r) in last:
        ans+=first[(r,b)]*last[(b,r)]
        
print(ans)

Submission status: Accepted

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

ans = 0

cand = defaultdict(int)
for bit in range(1 << n):
    red = []
    blue = []
    for i in range(n):
        if (bit >> i) & 1:
            red.append(s[i])
        else:
            blue.append(s[i])
    red = ''.join(red[::-1])
    blue = ''.join(blue[::-1])
    cand[(red, blue)] += 1

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

    red = ''.join(red)
    blue = ''.join(blue)
    ans += cand[(red, blue)]

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
string = input()
ans = 0
if string[:n] == string[2*n-1:n-1:-1]:
  ans += 2
for b in range(1,2**n-1):
  s = []
  t = []
  for c in range(n):
    if b & 2**c:
      s.append(string[c])
    else:
      t.append(string[c])
  s = s[::-1]
  t = t[::-1]
  ltr = string[n:]
  l = len(s)
  DP = [[0 for i in range(l+1)] for j in range(n+1)]
  DP[0][0] = 1
  for i in range(1,n+1):
    x = ltr[i-1]
    for j in range(0,min(i+1,l+1)):
      if j>=1 and s[j-1] == x:
        DP[i][j] += DP[i-1][j-1]
      if i-j<=len(t) and t[i-j-1] == x:
        DP[i][j] += DP[i-1][j]
  ans += DP[-1][-1]
print(ans)

Submission status: Accepted

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

def main():
    N = int(input())
    S = input()
    mae,usi = S[:N],S[N:][::-1]
    md,ud = defaultdict(int),defaultdict(int)
    
    for i in range(1<<N):
        mr,mb,ur,ub = "","","",""
        for j in range(N):
            if (i>>j)&1:
                mr += mae[j]
                ur += usi[j]
            else:
                mb += mae[j]
                ub += usi[j]
        md[(mr,mb)] += 1
        ud[(ur,ub)] += 1
    
    ans = 0
    for key,val in md.items():
        ans += ud[key]*val
        
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools
from fractions import gcd
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
_LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
N = NI()
S = input()
sr = S[-1:N - 1:-1]
ans = 0
fwd = []
rev = {}
for bit in range(2**N):
    red1 = ''
    blue1 = ''
    red2 = ''
    blue2 = ''
    b = 1
    for i in range(N):
        if b & bit:
            red1 += S[i]
            red2 += sr[i]
        else:
            blue1 += S[i]
            blue2 += sr[i]
        b <<= 1
    fwd.append(red1 + ' ' +  blue1)
    key = blue2 + ' ' + red2
    if key in rev:
        rev[key] += 1
    else:
        rev[key] = 1

for s in fwd:
    if s in rev:
        ans += rev[s]
print (ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
S = input()
cnt = defaultdict(dict)

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)
    
    if b not in cnt[r]:
        cnt[r][b] = 1
    else:
        cnt[r][b] += 1

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

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)
    
    if r in cnt[b]:
        ans += cnt[b][r]

print(ans)

Submission status: Accepted

Solution code:
def main():
    from collections import defaultdict

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

    dic = defaultdict(int)

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

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

    print (count)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import combinations
from collections import defaultdict

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

d = defaultdict(int)
left = set()

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

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

from itertools import product

N = I()
S = str(input())

# 右側半分の組の全列挙
d = defaultdict(lambda:defaultdict(int))
A = list(product([0,1],repeat=N))
for a in A:
    x = []
    y = []
    for i in range(N):
        if a[i]:
            x.append(S[N+i])
        else:
            y.append(S[N+i])
    x = ''.join(x)
    y = ''.join(y)
    d[x][y] += 1

# 左側半分で各塗り方を全列挙
# 右側半分の赤，青の値が決まる
ans = 0
for a in A:
    x = []
    y = []
    for i in range(N):
        if a[i]:
            x.append(S[i])
        else:
            y.append(S[i])
    x = ''.join(x[::-1])
    y = ''.join(y[::-1])
    ans += d[x][y]
    
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict as dd

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

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

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

Submission status: Accepted

Solution code:
import collections
d=collections.defaultdict(int)
n=int(input())
s=input()
def f(s,r,b,t):
    if t==n:
        d[(r,b)]+=1
        return
    f(s,r+s[t],b,t+1)
    f(s,r,b+s[t],t+1)
f(s[:n],"","",0)
d1=d
d=collections.defaultdict(int)
f(s[-1:n-1:-1],"","",0)
ans=0
for i,j in d.items():
    ans+=j*d1[i]
print(ans)

Submission status: Accepted

Solution code:

from collections import defaultdict


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

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

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

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

        dx[(red, blue)] += 1

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

        dy[(red, blue)] += 1

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
S = input()
S = S[:N]+S[2*N-1:N-1:-1]
ldic = defaultdict(int)
rdic = defaultdict(int)
for i in range(2**N):
  lred = ""
  lblue = ""
  rred = ""
  rblue = ""
  for j in range(N):
    if i%2==1:
      lred += S[j]
      rred += S[N+j]
    else:
      lblue += S[j]
      rblue += S[N+j]
    i >>= 1
  ldic[(lred,lblue)] += 1
  rdic[(rred,rblue)] += 1

ans = 0
for k in ldic.keys():
  ans += ldic[k]*rdic[k]
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, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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:
		red_f, blue_f = key.split(",")
		ans += dic_f[key]*dic_l[key]
	print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

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

d = defaultdict(int)
left = set()
for r in range(n+1):
    for cl in combinations(range(n),r):
        sl = ""
        sr = ""
        for i in range(n):
            if i in cl:
                sl += s[i]
            else:
                sr += s[i]
        left.add(sl+","+sr)
        d[sl+","+sr] += 1

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

print(res)

Submission status: Accepted

Solution code:
N=int(input());S=input();
SL=S[:N];SR=S[N:];SR=SR[::-1]
MR={};ans=0
for i in range(2**N):
  R="";B="";
  for j in range(N):
    if(i%2):
      R+=SL[j]
    else:
      B+=SL[j]
    i//=2
  if R+"_"+B in MR: 
    MR[R+"_"+B]+=1
  else:
    MR[R+"_"+B]=1
for i in range(2**N):
  R="";B="";
  for j in range(N):
    if(i%2):
      R+=SR[j]
    else:
      B+=SR[j]
    i//=2
  if R+"_"+B in MR: 
    ans+=MR[R+"_"+B]
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n=int(input())
s=input()
s1=s[:n]
s2=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(s1,i)]+=1
for i in range(2**n):
  ans+=d[paint(s2,i)]
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

def main():
  n = int(input())
  S = input()
  A = S[:n]
  B = S[n:][::-1]
  ans = 0
  La = []
  for i in range(2**n):
    a1, a2 = "", ""
    for j in range(n):
      if i>>j & 1:
        a1 += A[j]
      else:
        a2 += A[j]
    La.append(a1+"#"+a2)

  Da = Counter(La)

  for i in range(2**n):
    b1, b2 = "", ""
    for j in range(n):
      if i>>j & 1:
        b1 += B[j]
      else:
        b2 += B[j]
    ans += Da[b1+"#"+b2]

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

S = S[::-1]
cnt_right = defaultdict(int)
for i in range(2 ** N):
    a, b = "", ""
    for j in range(N):
        if (i >> j) & 1:
            a += S[j]
        else:
            b += S[j]
    cnt_right[(a, b)] += 1
    
answer = 0
for k in cnt_left.keys():
    answer += cnt_left[k] * cnt_right[k]
print(answer)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
N = int(input())
S = input()
Sl = list(S[:N])
Sr = list(reversed(S[N:]))
d_l = defaultdict(int)
d_r = defaultdict(int)
for s in range(1<<N):
    sl1 = ''
    sl2 = ''
    sr1 = ''
    sr2 = ''
    for i in range(N):
        if s&(1<<i):
            sl1+=Sl[i]
            sr1+=Sr[i]
        else:
            sl2+=Sl[i]
            sr2+=Sr[i]
    d_l[sl1+' '+sl2]+=1
    d_r[sr1+' '+sr2]+=1
ans = 0
for k, v in d_l.items():
    ans += d_r[k]*v
print(ans)

Submission status: Accepted

Solution code:
# AGC026c
ans = 0


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    # map(int, input().split())

    n = int(input())
    s = input()[:-1]
    sLatter = s[n:][::-1]

    d = dict()

    def dfs1(i, sR, sB):
        if i == n:
            if not (sR, sB[::-1]) in d:
                d[(sR, sB[::-1])] = 0
            d[(sR, sB[::-1])] += 1
            return
        dfs1(i + 1, sR + s[i], sB)
        dfs1(i + 1, sR, sB + s[i])

    dfs1(0, '', '')
    # print(d)

    def dfs2(i, sR, sB):
        if i == n:
            if (sR, sB[::-1]) in d:
                global ans
                ans += d[(sR, sB[::-1])]
            return
        dfs2(i + 1, sR + sLatter[i], sB)
        dfs2(i + 1, sR, sB + sLatter[i])

    dfs2(0, '', '')
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import combinations as combi
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
S = list(input())[: -1]
d = dd(int)
res = 0
for r in range(N + 1):
  for c in combi([x for x in range(N)], r):
    x = []
    y = []
    for i in range(N):
      if i in c: x.append(S[i])
      else: y.append(S[i])
    d["".join(x) + "?" + "".join(y)] += 1

for b in range(N + 1):
  for c in combi([x + N for x in range(N)], b):
    x = []
    y = []
    for i in range(N, N * 2):
      if i in c: x.append(S[i])
      else: y.append(S[i])
    x = x[: : -1]
    y = y[: : -1]
    res += d["".join(x) + "?" + "".join(y)]
print(res)

Submission status: Accepted

Solution code:
import sys
from itertools import combinations as combi
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
S = list(input())[: -1]
res = 0
s = S[: N]
t = S[N: ]
a = dd(int)
b = dd(int)
for i in range(N + 1):
  for c in combi([x for x in range(N)], i):
    u = []
    v = []
    for j in range(N):
      if j in c: u.append(s[j])
      else: v.append(s[j])
    a["".join(u) + "?" + "".join(v)] += 1
#print(a)
for i in range(N + 1):
  for c in combi([x for x in range(N)], i):
    u = []
    v = []
    for j in range(N):
      if j in c: u.append(t[j])
      else: v.append(t[j])
    b["".join(u) + "?" + "".join(v)] += 1
for ak in a.keys():
  bk = ak[: : -1]
  res += a[ak] * b[bk]
print(res)

Submission status: Accepted

Solution code:
n = int(input())
string = input()
ans = 0
if string[:n] == string[2*n-1:n-1:-1]:
  ans += 2
for b in range(1,2**n-1):
  s = ""
  t = ""
  for c in range(n):
    if b & 2**c:
      s += string[c]
    else:
      t += string[c]
  s = s[::-1]
  t = t[::-1]
  ltr = string[n:]
  l = len(s)
  DP = [[0 for i in range(l+1)] for j in range(n+1)]
  DP[0][0] = 1
  for i in range(1,n+1):
    x = ltr[i-1]
    for j in range(0,min(i+1,l+1)):
      if j>=1 and s[j-1] == x:
        DP[i][j] += DP[i-1][j-1]
      if i-j<=len(t) and t[i-j-1] == x:
        DP[i][j] += DP[i-1][j]
  ans += DP[-1][-1]
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))

from collections import defaultdict

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

    tmp = defaultdict(lambda : 0)
    for state in range(1 << n):
        rs, bs = "", ""
        for i in range(n):
            if (state >> i) & 1:
                rs += s[i]
            else:
                bs += s[i]
        tmp[(rs, bs)] += 1
    
    ans = 0
    for state in range(1 << n):
        rs, bs = "", ""
        for i in range(n):
            if (state >> i) & 1:
                rs += s[-i - 1]
            else:
                bs += s[-i - 1]
        ans += tmp[(rs, bs)]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import combinations


def solve():
    N = int(input())
    S = input()
    s1, s2 = S[:N], S[N:][::-1]
    
    l_dict = defaultdict(int)
    r_dict = defaultdict(int)
    for i in range(N+1):
        for red_idx in combinations(range(N), i):
            red, blue = '', ''
            for j in range(N):
                if j in red_idx:
                    red += s1[j]
                else:
                    blue += s1[j]
            l_dict[red+' '+blue] += 1
    for i in range(N+1):
        for red_idx in combinations(range(N), i):
            red, blue = '', ''
            for j in range(N):
                if j in red_idx:
                    red += s2[j]
                else:
                    blue += s2[j]
            r_dict[red+' '+blue] += 1
    
    ans = sum(l_dict[key] * r_dict[key] for key in l_dict)
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def examA():
    N = I()
    A = LI()
    ans = 0
    for i in range(N-1):
        if A[i+1]==A[i]:
            A[i+1] = 101
            ans +=1
    print(ans)
    return

def examB():
    T = I()
    ans = ["Yes"]*T
    for i in range(T):
        A, B, C, D = LI()
        if A<B:
            ans[i] = "No"
            continue
        if D<B:
            ans[i] = "No"
            continue
        if C>=B:
            continue


    return

def examC():
    N = I()
    S = SI()
    d1 = defaultdict(int)
    d2 = defaultdict(int)
    loop = 2**N
    for i in range(loop):
        curR = ""; curB = ""
        curR2 = ""; curB2 = ""
        for j in range(N):
            if i&(1<<j)==(1<<j):
                curR +=S[j]
                curR2 +=S[j+N]
            else:
                curB +=S[j]
                curB2 +=S[j+N]
        d1[(curR,curB)] +=1
        d2[(curR2,curB2)] +=1
    ans = 0
    for key,i in d1.items():
        cur = i*d2[(key[1][::-1],key[0][::-1])]
        ans +=cur
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,inf
mod = 10**9 + 7
inf = 10**18

if __name__ == '__main__':
    examC()

Submission status: Accepted

Solution code:
N=int(input())
S=list(input())
left=S[:N]
right=S[N:][::-1]
ans=0
for i in range(2**N):
    red=[]
    blue=[]
    for j in range(N):
        if (i>>j)&1==1:
            red.append(S[j])
        else:
            blue.append(S[j])
    L=len(red)
    if L==0 or L==N:
        if right==left:
            ans+=1
        continue
    dp=[[0]*L for _ in range(N)]
    zero=0
    if right[0]==red[0]:
        dp[0][0]=1
    if right[0]==blue[0]:
        zero=1
    for j in range(1,N):
        if right[j]==red[0]:
            dp[j][0]=zero
        if j-1+L<N and right[j]==blue[j-1]:
            dp[j][0]+=dp[j-1][0]
        if j+L<N and right[j]==blue[j]:
            zero*=1
        else:
            zero=0
        for k in range(1,min( j+1,len(red))):
            if right[j]==red[k]:
                dp[j][k]+=dp[j-1][k-1]
            if j-k<=N-L and right[j]==blue[j-k-1]:
                dp[j][k]+=dp[j-1][k]
    ans+=dp[N-1][-1]
print(ans)

Submission status: Accepted

Solution code:
def main():
    from collections import defaultdict

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

    L, R = S[:N], S[N * 2 - 1:N - 1:-1]

    def make_counter(s: str) -> defaultdict(int):
        ret = defaultdict(int)
        for bit in range(1 << N):
            red, blue = '', ''
            for j in range(N):
                if (bit >> j) & 1:
                    red += s[j]
                else:
                    blue += s[j]

            ret[red + '_' + blue] += 1
        return ret

    ld = make_counter(L)
    rd = make_counter(R)

    print(sum(ld[key] * rd[key] for key in ld))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from collections import defaultdict
def resolve():
    n=int(input())
    S=input()
    S,T=S[:n],S[2*n-1:n-1:-1]
    C=defaultdict(int)

    for V in range(1<<n):
        s=''.join([s if((V>>i)&1) else '' for i,s in enumerate(S)])
        t=''.join([s if(not (V>>i)&1) else '' for i,s in enumerate(S)])
        C[(s,t)]+=1

    ans=0
    for V in range(1<<n):
        s=''.join([t if((V>>i)&1) else '' for i,t in enumerate(T)])
        t=''.join([t if(not (V>>i)&1) else '' for i,t in enumerate(T)])
        ans+=C[(s,t)]

    print(ans)
resolve()

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    s=input()
    d1=dict()
    d2=dict()
    temp1=[None]*n
    temp2=[None]*n
    for ii in range(2**n):
        i=("0"*n+bin(ii)[2:])[-n:]
        cnt1=0
        cnt2=n-1
        for k,j in enumerate(i):
            if j=="1":
                temp1[cnt1]=s[k]
                temp2[cnt1]=s[2*n-k-1]
                cnt1+=1
            else:
                temp1[cnt2]=s[k]
                temp2[cnt2]=s[2*n-k-1]
                cnt2-=1
        t1="".join(temp1)
        t2="".join(temp2)
        if (t1,cnt1) not in d1.keys():
            d1[(t1,cnt1)]=1
        else:
            d1[(t1,cnt1)]+=1
        if (t2,cnt1) not in d2.keys():
            d2[(t2,cnt1)]=1
        else:
            d2[(t2,cnt1)]+=1
    ans=0
    for i,j in d1.items():
        if i in d2.keys():
            ans+=j*d2[i]
    print(ans)
main()