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 Counter
from itertools import product
N = int(input())
S = input()
Left = Counter()
Right = Counter()
S_left = S[:N]
S_right = S[2*N-1:N-1:-1]
for B in product(range(2),repeat = N):
    red_left = ''
    blue_left = ''
    red_right = ''
    blue_right = ''
    for i in range(N):
        if B[i]:
            red_left += S_left[i]
            red_right += S_right[i]
        else:
            blue_left += S_left[i]
            blue_right += S_right[i]
    Left[red_left + '|' + blue_left] += 1
    Right[blue_right + '|' + red_right] += 1
ans = 0
for i in Left.keys():
    ans += Left[i]*Right[i]
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import product

n = int(input())
s = list(input())
s_l = list(reversed(s[n:]))

red = Counter(["".join([s[i] for i in range(n) if bit[i] == 1] + ["|"] + [s[i] for i in range(n) if bit[i] == 0]) for bit in product(range(2), repeat=n)])
blue = Counter(["".join([s_l[i] for i in range(n) if bit[i] == 1] + ["|"] + [s_l[i] for i in range(n) if bit[i] == 0]) for bit in product(range(2), repeat=n)])

ans = 0

for key, value in red.items():
	ans += value * blue[key]

print(ans)

Submission status: Accepted

Solution code:
import collections

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

s1 = s[:n]
s2 = s[-1:-(n + 1):-1]

s_1 = collections.defaultdict(int)
s_2 = collections.defaultdict(int)
for i in range(2 ** n):
    bin_i = bin(i + 2 ** n)
    sequence1 = ""
    sequence1_inverse = ""
    sequence2 = ""
    sequence2_inverse = ""
    for j in range(n):
        if bin_i[j + 3] == "1":
            sequence1 += s1[j]
            sequence2 += s2[j]
        else:
            sequence1_inverse += s1[j]
            sequence2_inverse += s2[j]
    s_1[sequence1 + "-" + sequence1_inverse] += 1     
    s_2[sequence2 + "-" + sequence2_inverse] += 1
ans = 0
for i in dict(s_1):
    ans += s_1.get(i, 0) * s_2.get(i, 0)
    '''
    if i in dict(s_2):
        ans += dict(s_1)[i] * dict(s_2)[i]
    '''
print(ans)

Submission status: Accepted

Solution code:
import collections

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

s1 = s[:n]
s2 = s[-1:-(n + 1):-1]

s_1 = collections.defaultdict(int)
s_2 = collections.defaultdict(int)

strlist = []

for i in range(2 ** n):
    bin_i = bin(i + 2 ** n)
    sequence1 = ""
    sequence1_inverse = ""
    sequence2 = ""
    sequence2_inverse = ""
    for j in range(n):
        if bin_i[j + 3] == "1":
            sequence1 += s1[j]
            sequence2 += s2[j]
        else:
            sequence1_inverse += s1[j]
            sequence2_inverse += s2[j]
    s_1[sequence1 + "-" + sequence1_inverse] += 1     
    s_2[sequence2 + "-" + sequence2_inverse] += 1
ans = 0

for i in dict(s_1):
    ans += s_1.get(i, 0) * s_2.get(i, 0)
    '''
    if i in dict(s_2):
        ans += dict(s_1)[i] * dict(s_2)[i]
    '''
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

S1 = S[:N]
S2 = S[N:][::-1]

ans = 0
D = defaultdict(int)

for i in range(2**N):
    bit = bin(2**N+i)[3:]

    red1 = "".join([d for d, s in zip(S1, bit) if s == "1"])
    blue1 = "".join([d for d, s in zip(S1, bit) if s == "0"])
    D[(red1, blue1)] += 1

for i in range(2**N):
    bit = bin(2 ** N + i)[3:]

    red2 = "".join([d for d, s in zip(S2, bit) if s == "1"])
    blue2 = "".join([d for d, s in zip(S2, bit) if s == "0"])
    ans += D[(blue2, red2)]

print(ans)

Submission status: Accepted

Solution code:
import itertools
from collections import Counter

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

t=s[:n][::-1]
u=s[n:]
tc=Counter()
uc=Counter()
for i in itertools.product(range(2),repeat=n):
	t0=""
	t1=""
	u0=""
	u1=""
	for j in range(n):
		if not i[j]:
			t0+=t[j]
			u0+=u[j]
		else:
			t1+=t[j]
			u1+=u[j]
	tc[t0+"-"+t1]+=1
	uc[u0+"-"+u1]+=1

ans=0
for i in tc.keys():
	ans+=tc[i]*uc[i]
print(ans)

Submission status: Accepted

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

sleft = S[:N]
sright = S[2*N:N-1:-1]
ldict,rchoise = {},[]
count = 0
for i in range(2**N):
    red = bin(i)[2:].zfill(N)
    leftred, rightred, leftblue, rightblue = "","","",""
    for j in range(N):
        if red[j] == "1":
            leftred += sleft[j]
            rightred += sright[j]
        else:
            leftblue += sleft[j]
            rightblue += sright[j]
    if leftred + "-" + leftblue in ldict.keys():
        ldict[leftred + "-" + leftblue] += 1
    else:
        ldict[leftred + "-" + leftblue] = 1
    rchoise.append(rightred + "-" + rightblue)
    
for i in rchoise:
    count += ldict.get(i, 0)
print(count)

Submission status: Accepted

Solution code:
import sys
import socket
 
if socket.gethostname() in ['N551J', 'F551C']:
    sys.stdin = open('c1.in')
 
 
def read_int_list():
    return list(map(int, input().split()))
 
 
def read_int():
    return int(input())
 
 
def read_str_list():
    return input().split()
 
 
def read_str():
    return input()
 
 
def solve():
    n = read_int()
    s = read_str()

    #同じ文字が連続する場合、redとblueに振り分ける順番が変わってもそのあとの判定に影響を与えないので、計算結果をcasheに格納して同一計算を省略する
    cache = {}

    #1文字ずつredとblueに振り分けながら再帰的に関数読み出しを繰り返し、条件を満たしながらredとblue双方の長さが2nになったものの数を数える
    #探索数は基本的に2のn乗でスケールするが、条件に当てはまらないような塗分けは排除しながら進んでいく（再帰読み出しを行わず戻り値0を返す）
    def rec(red, blue):
        #一度探索したことのある文字列は即答する
        if (red, blue) in cache:
            return cache[(red, blue)]

        nr = len(red)
        nb = len(blue)

        #redとblueのどちらかが長さnを超えていたら関数は0を返す
        if nr > n or nb > n:
            res = 0
            cache[(red, blue)] = res
            return res
        #長さの合計がちょうど2nなら（上記と合わせると、両方の長さがnずつならば関数は1を返す）
        if nr + nb == 2 * n:
            res = 1
            cache[(red, blue)] = res
            return res
        c = s[nr + nb]
        res = 0

        #文字列sの一番左の文字から始め、1文字ずつredの左側もしくはblueの右側に格納していく
        #nr+nbがn未満の場合無条件で再帰的関数読み出しを行う
        #nr+nbがnを超えた場合、新しく追加する文字cがこれまでのred, blueと整合性が取れている場合のみに再帰的関数読み出しを行う
        if nr + nb < n or (nr < n and c == blue[nr - n]):
            res += rec(red + c, blue)
        if nr + nb < n or (nb < n and c == red[n - 1 - nb]):
            res += rec(red, c + blue)

        
        cache[(red, blue)] = res
        return res

    res2 = rec('', '')
    return res2
 
 
def main():
    res = solve()
    print(res)
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
n=i1()
s=input()
from collections import defaultdict
ad1 = defaultdict(int)
ad2 = defaultdict(int)

for i in range(1<<n):
 a=""
 b=""
 for j in range(n):
  if i & (1<<j) ==0:
     a+=s[j]
  else:
     b+=s[j]
 ad1[a+"_"+b[::-1]]+=1
 a=""
 b=""
 for j in range(n):
  if i & (1<<j):
     a+=s[j+n]
  else:
     b+=s[j+n]
 ad2[b[::-1]+"_"+a]+=1
 
cc=0
for i in ad1.keys():
 cc+=ad1[i]*ad2[i]

print(cc)

Submission status: Accepted

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

S1, S2 = S[:N], S[N:][::-1]

dic = {}
keys = []
Ans = 0

for i in range(2 ** N):
    red, blue, red2, blue2 = "", "", "", ""
    # 半分ずつbit全探索
    bits = bin(2 ** N + i)[3:]
    for j in range(N):
        if bits[j] == "0":
            red += S1[j]
            red2 += S2[j]
        else:
            blue += S1[j]
            blue2 += S2[j]
    # あとで数える際に使うので記録しておく
    keys.append(red2 + "-" + blue2)
    # 半分全列挙
    key = red + "-" + blue
    if key not in dic.keys():
        dic[key] = 1
    else:
        dic[key] += 1

for key in keys:
    Ans += dic.get(key, 0)

print(Ans)

Submission status: Accepted

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

result = 0

S1 = S[:N]
S2 = S[N:][::-1]

def calc(s, x):
    s1 = ""
    s2 = ""
    for c in s:
        if x & 1:
            s1 += c
        else:
            s2 += c
        x >>= 1
    return s1, s2

from collections import defaultdict

kv = defaultdict(int)

for i in range(2**N):
    kv[calc(S2, i)] += 1

for i in range(2**N):
    result += kv[calc(S1, i)]

print(result)

Submission status: Accepted

Solution code:
import itertools
#import math
#from collections import deque

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

t=s[:n][::-1]
u=s[n:]
dic=dict()
for i in itertools.product(range(2),repeat=n):
	t_=[""]*2
	u_=[""]*2
	for j in range(n):
		t_[i[j]]+=t[j]
		u_[i[j]]+=u[j]
	if (t_[0],t_[1]) not in dic:
		dic[(t_[0],t_[1])]=[1,0]
	else:
		dic[(t_[0],t_[1])][0]+=1
	if (u_[0],u_[1]) not in dic:
		dic[(u_[0],u_[1])]=[0,1]
	else:
		dic[(u_[0],u_[1])][1]+=1

ans=0
for i in dic.keys():
	ans+=dic[i][0]*dic[i][1]
print(ans)

Submission status: Accepted

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

S1,S2 = S[:N],S[N:][::-1]

dic = {}
keys = []
Ans = 0

for i in range(2**N):
    red,blue,red2,blue2 = "","","",""
    # 半分ずつbit全探索
    bits = bin(2**N+i)[3:]
    for j in range(N):
        if bits[j]=="0":
            red  += S1[j]
            red2 += S2[j]
        else:
            blue += S1[j]
            blue2 += S2[j]
    # あとで数える際に使うので記録しておく
    keys.append(red2+"-"+blue2)
    # 半分全列挙
    key = red+"-"+blue
    if key not in dic.keys():
        dic[key] = 1
    else:
        dic[key] += 1

for key in keys:
    Ans += dic.get(key,0)

print(Ans)

Submission status: Accepted

Solution code:
# encoding:utf-8

import itertools
from collections import defaultdict


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

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

	ans = 0
	#print(left, right)
	for n_r in range(n+1):
		d_left = defaultdict(lambda: 0)
		d_right = defaultdict(lambda: 0)
		#print([1 if x >= n_r else 0 for x in range(n)])
		pts = itertools.combinations(list(range(n)), r = n_r)
		
		for pt in pts:
			#print(pt)
			b_l = ""
			r_l = ""
			b_r = ""
			r_r = ""
			for i in range(n):
				if i in pt:
					b_l += left[i]
					b_r += right[i]
				else:
					r_l += left[i]
					r_r += right[i]

			d_left[(b_l, r_l)] += 1
			d_right[(b_r, r_r)] += 1

		for key in d_left:
#			print(n_r, key, d_left[key], d_right[key])
			ans += d_left[key] * d_right[key]

	print(ans)

	

if __name__ == '__main__':
	main()

Submission status: Accepted

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

S1,S2 = S[:N],S[N:][::-1]

dic = {}
Ans = 0
keys = []

for i in range(2**N):
    red,blue = "",""
    red2,blue2 = "",""
    bits = bin(2**N+i)[3:]
    for j in range(N):
        if bits[j]=="0":
            red   += S1[j]
            red2 += S2[j]
        else:
            blue += S1[j]
            blue2 += S2[j]
    keys.append(red2+"-"+blue2)
    key = red+"-"+blue
    if key not in dic.keys():
        dic[key] = 1
    else:
        dic[key] += 1

for k in keys:
    Ans += dic.get(k,0)

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[:-N-1:-1]
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 k,v in ctr1.items():
    ans += v * ctr2[k]
print(ans)

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

N = read()
S = input()

former = defaultdict(lambda: 0)
latter = defaultdict(lambda: 0)

def power(n):
  return chain(*(combinations(range(n), r) for r in range(n+1)))

def solve(N, S):
  for p in power(N):
    bs1 = []; rs1 = []; bs2 = []; rs2 = []
    for i in range(N):
      if i in p:
        rs1.append(S[i])
        rs2.append(S[-1-i])
      else:
        bs1.append(S[i])
        bs2.append(S[-1-i])
    former["".join(rs1), "".join(bs1)] += 1
    latter["".join(bs2), "".join(rs2)] += 1

  ans = 0
  for k, v in former.items():
    if k in latter:
      ans += v * latter[k]

  return ans

print(solve(N, S))

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

N = read()
S = input()

ans = 0

for bits in range(2**N):
  bs = []; rs = []
  for i in range(N):
    if ((1 << i) & bits) == 0:
      rs.append(S[i])
    else:
      bs.append(S[i])
  rs.reverse(); bs.reverse()

  lenr = len(rs); lenb = len(bs)
  dp = [[0] * (lenb + 1) for _ in range(lenr + 1)]
  dp[0][0] = 1
  for i in range(lenr + 1):
    for j in range(lenb + 1):
      if i < lenr and rs[i] == S[N+i+j]:
        dp[i+1][j] += dp[i][j]
      if j < lenb and bs[j] == S[N+i+j]:
        dp[i][j+1] += dp[i][j]
  ans += dp[-1][-1]

print(ans)

Submission status: Accepted

Solution code:

import sys
#sys.stdin=open("data.txt")
input=sys.stdin.readline

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

memo={}
def getans(a,b,c):
    while a and c and a[0]==c[-1]:
        a=a[1:]
        c=c[:-1]
    if a and c: return 0
    if b=="":
        if a=="" and c=="": return 1
        else: return 0
    key=a+"/"+b+"/"+c
    if key in memo: return memo[key]
    # select first letter
    ans=0
    for i in range(1,len(b)):
        if b[0]==b[i]:
            ans+=getans(a,b[1:i],b[i+1:]+c)
    # don't select first letter
    ans+=getans(a+b[0],b[1:],c)
    memo[key]=ans
    #print(key,ans)
    return ans

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

#print(len(memo))

Submission status: Accepted

Solution code:
#!/usr/bin/env python

import sys
import math
import itertools as it
from collections import deque

sys.setrecursionlimit(10000000)

def func():
    N = input()
    S = raw_input()

    S1 = S[:N]
    S2 = S[N:]

    m = {}

    for i in range((1 << N)):
        s1 = s2 = ''
        for j in range(N):
            if(i & (1 << j)):
                s1 = s1 + S1[j]
            else:
                s2 = S1[j] + s2
        if (s1, s2) in m:
            m[(s1, s2)] += 1
        else:
            m[(s1, s2)] = 1

    ans = 0

    for i in range((1 << N)):
        s1 = s2 = ''
        for j in range(N):
            if(i & (1 << j)):
                s1 = S2[j] + s1
            else:
                s2 = s2 + S2[j]
        if (s1, s2) in m:
            ans += m[(s1, s2)]

    print ans

func()

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import combinations


def get_pair(s, cmb):
    g, h = 0, 0
    for i in range(n):
        if i in cmb:
            g <<= 5
            g += s[i]
        else:
            h <<= 5
            h += s[i]
    return g, h


def patterns(k, d, e):
    ret = 0
    f = defaultdict(int)
    for cmb in combinations(range(n), k):
        f[get_pair(d, cmb)] += 1
    for cmb in combinations(range(n), k):
        ret += f[get_pair(e, cmb)]
    return ret


def solve(n, b):
    d = b[:n]
    e = b[2 * n - 1:n - 1:-1]
    ans = 0

    if n % 2 == 0:
        for k in range(n // 2):
            ans += 2 * patterns(k, d, e)
        ans += patterns(n // 2, d, e)
    else:
        for k in range(n // 2 + 1):
            ans += 2 * patterns(k, d, e)
    return ans


n = int(input())
s = input()
a = ord('a') - 1
b = [ord(c) - a for c in s]
print(solve(n, b))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().strip().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def ref_slv(N, S):
    ans = 0

    for i in combinations(range(0, 2*N), N):
        l = []
        r = []
        for j in range(2*N):
            if j in i:
                l.append(S[j])
            else:
                r.append(S[j])

        if ''.join(l) == ''.join(reversed(r)):
            ans += 1

    return ans


@mt
def slv(N, S):
    ans = 0

    l = S[:N]
    r = S[N:][::-1]
    ld = defaultdict(lambda: 0)
    rd = defaultdict(lambda: 0)

    for i in range(N+1):
        for j in combinations(range(N), i):
            lb = []
            lr = []
            rb = []
            rr = []
            for k in range(N):
                if k in j:
                    lb.append(l[k])
                    rr.append(r[k])
                else:
                    lr.append(l[k])
                    rb.append(r[k])
            ld[(''.join(lr), ''.join(lb))] += 1
            rd[(''.join(rr), ''.join(rb))] += 1
    for k, v in ld.items():
        if k in rd:
            ans += v * rd[k]

    return ans


def main():
    # for i in range(1, 19):
    #     print(i, slv(i, ""))
    N = read_int()
    S = read_str()
    print(slv(N, S))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

    cand1 = collections.defaultdict(int)
    cand2 = collections.defaultdict(int)

    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]
        cand1[(red,blue)] += 1

        red = ''
        blue = ''
        for i in xrange(n):
            ci = (mask>>i) & 1
            if ci:
                red += s[2*n-i-1]
            else:
                blue += s[2*n-i-1]
        cand2[(red,blue)] += 1

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

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

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:]):
        dp2 = [0] * (lenF + 1)
        for j in range(lenF + 1):
            if dp[j] == 0: continue
            if j < lenF and s == Fs[j]:
                dp2[j+1] += dp[j]
            if 0 <= i-j < lenG and s == Gs[i-j]:
                dp2[j] += dp[j]
        dp = dp2

    ans += dp[lenF]

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = input()
Sl = S[:N]
Sr = S[N:]

from collections import defaultdict
L = defaultdict(int)
R = defaultdict(int)
for i in range(1<<N):
    t1 = ""
    t2 = ""
    for j in range(N):
        if i & (1<<j):
            t1 += Sl[j]
    for j in range(N-1, -1, -1):
        if not i & (1<<j):
            t2 += Sl[j]
    L[(t1, t2)] += 1
    t1 = ""
    t2 = ""
    for j in range(N-1, -1, -1):
        if i & (1<<j):
            t1 += Sr[j]
    for j in range(N):
        if not i & (1<<j):
            t2 += Sr[j]
    R[(t1, t2)] += 1
ans = 0
for k, v in L.items():
    ans += R[k] * v
print(ans)

Submission status: Accepted

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

memo = {}
def dp(s1, s2, l1, l2, r1, r2, i):
  #print(i, s1 + '|' +s2)
  if s1 + s2 in memo:
    return memo[s1 + s2]
  if i == 2 * N:
    ret = int(s1 == s2)
  else:
    ret = 0
    if i % 2 == 0:
      c = S[i // 2]
      # S1のl1か、S2のr2に入れる
      if s1[l1] == ' ' and (s2[l1] == ' ' or s2[l1] == c):
        ret += dp(s1[:l1] + c + s1[l1+1:], s2, l1+1, l2, r1, r2, i+1)
      if s2[r2] == ' ' and (s1[r2] == ' ' or s1[r2] == c):
        ret += dp(s1, s2[:r2] + c + s2[r2+1:], l1, l2, r1, r2-1, i+1)
    else:
      c = S[-(i // 2 + 1)]
      # S2のl2か、S1のr1に入れる
      if s1[r1] == ' ' and (s2[r1] == ' ' or s2[r1] == c):
        ret += dp(s1[:r1] + c + s1[r1+1:], s2, l1, l2, r1-1, r2, i+1)
      if s2[l2] == ' ' and (s1[l2] == ' ' or s1[l2] == c):
        ret += dp(s1, s2[:l2] + c + s2[l2+1:], l1, l2+1, r1, r2, i+1)
  memo[s1 + s2] = ret
  return ret


a = S[0] + (' ' * (N-1))
b = ' ' * N

print(dp(a, b, 1, 0, N-1, N-1, 1) * 2)

Submission status: Accepted

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

dict_1 = dict()
q_list = [""]*(2**N)
res = 0

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

Submission status: Accepted

Solution code:
import sys
import socket

if socket.gethostname() in ['N551J', 'F551C']:
    sys.stdin = open('c1.in')


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


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


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

    cache = {}

    def rec(red, blue):
        if (red, blue) in cache:
            return cache[(red, blue)]
        nr = len(red)
        nb = len(blue)
        if nr > n or nb > n:
            res = 0
            cache[(red, blue)] = res
            return res
        if nr + nb == 2 * n:
            res = 1
            cache[(red, blue)] = res
            return res
        c = s[nr + nb]
        res = 0
        if nr + nb < n or (nr < n and c == blue[nr - n]):
            res += rec(red + c, blue)
        if nr + nb < n or (nb < n and c == red[n - 1 - nb]):
            res += rec(red, c + blue)
        cache[(red, blue)] = res
        return res

    res2 = rec('', '')
    return res2


def main():
    res = solve()
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

if sys.version[0] == '2':
    range, input = xrange, raw_input

from collections import defaultdict
N = int(input())
S = input()
first, second = S[:N], S[N:]

s_set = defaultdict(int)

def make_str(bit, s):
    red = []
    blue = []
    for i in range(N):
        if bit >> i & 1:
            red.append(s[i])
        else:
            blue.append(s[i])
    return ''.join(red), ''.join(blue[::-1])

for bit in range(1 << N):
    s_set[make_str(bit, second)] += 1

ans = 0
for bit in range(1 << N):
    red, blue = make_str(bit, first)
    ans += s_set[blue, red]
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
N = int(input())
S = input()
r = [0, 1]
ans = 0
d = [{} for i in range(N+1)]
for p in product(r, repeat=N):
    s = []
    for i in range(N):
        if p[i]:
            s.append(S[i])
    for i in range(N-1, -1, -1):
        if p[i] == 0:
            s.append(S[i])
    l = sum(p)
    s = "".join(s)
    d[l][s] = d[l].get(s, 0) + 1
for p in product(r, repeat=N):
    s = []
    for i in range(N-1, -1, -1):
        if p[i]:
            s.append(S[i+N])
    for i in range(N):
        if p[i] == 0:
            s.append(S[i+N])
    l = sum(p)
    s = "".join(s)
    ans += d[l].get(s, 0)
print(ans)

Submission status: Accepted

Solution code:

import sys
#sys.stdin=open("data.txt")
input=sys.stdin.readline

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

memo={}
def getans(a,b,c):
    while a and c and a[0]==c[-1]:
        a=a[1:]
        c=c[:-1]
    if b=="":
        if a=="" and c=="": return 1
        else: return 0
    key=a+"/"+b+"/"+c
    if key in memo: return memo[key]
    # select first letter
    ans=0
    for i in range(1,len(b)):
        if b[0]==b[i]:
            ans+=getans(a,b[1:i],b[i+1:]+c)
    # don't select first letter
    ans+=getans(a+b[0],b[1:],c)
    memo[key]=ans
    #print(key,ans)
    return ans

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

#print(len(memo))

Submission status: Runtime Error

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: Runtime Error

Solution code:
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: Runtime Error

Solution code:
from collections import defaultdict

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

d = defaultdict(int)
ans = 0

def paint(str, ptn):
  return (red, blue)

for i in range(2**N):
  red = ''.join(s for j, s in enumerate(first) if 2**j & ptn)
  blue = ''.join(s for j, s in enumerate(first) if not 2**j & ptn)
  d[paint(red, blue)] += 1
  
for i in range(2**N):
  red = ''.join(s for j, s in enumerate(last) if 2**j & ptn)
  blue = ''.join(s for j, s in enumerate(last) if not 2**j & ptn)
  ans += d[paint(red, blue)]
  
print(ans)

Submission status: Runtime Error

Solution code:
import collections

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

s1 = s[:n]
s2 = s[-1:-(n + 1):-1]

s_1 = collections.defaultdict(int)
s_2 = collections.defaultdict(int)h
for i in range(2 ** n):
    bin_i = bin(i + 2 ** n)
    sequence1 = ""
    sequence1_inverse = ""
    sequence2 = ""
    sequence2_inverse = ""
    for j in range(n):
        if bin_i[j + 3] == "1":
            sequence1 += s1[j]
            sequence2 += s2[j]
        else:
            sequence1_inverse += s1[j]
            sequence2_inverse += s2[j]
    s_1[sequence1 + "-" + sequence1_inverse] += 1     
    s_2[sequence2 + "-" + sequence2_inverse] += 1
ans = 0
for i in dict(s_1):
    ans += s_1.get(i, 0) * s_2.get(i, 0)
    '''
    if i in dict(s_2):
        ans += dict(s_1)[i] * dict(s_2)[i]
    '''
print(ans)

Submission status: Runtime Error

Solution code:


import math
aa=int(input())
N=[0 for i in range(aa)]
for i in range(aa):
  bb=input()
  #print(b)
  N[i]=bb.split()


def so(p,q):
  while p!=q:
    if p>q:
      p-=q
    else:
      q-=p
  return p


#print(so(11,5))

def aaa(n):

  a=int(N[n][0])
  b=int(N[n][1])
  c=int(N[n][2])
  d=int(N[n][3])

  e=a-a//b*b
  f=d-d//b*b
  
  if e*f>0 :
    s=gcd(e,f)
  else :
    s=f


  if a<b or d<b :
    return "No"
  
  elif b<=c :
    return "Yes"
  else:
  
    if f!=0 :
      ss=b//s*s
      if ss==b:
        ss-=s

      if ss>c:
        return "No"
          
    

        #print(e)
        #print(f)
  #print("while")
    else:
      if e>c :
        return "No"

  return "Yes"

for i in range(aa):
  print(aaa(i))