Problem:


問題 E : Pattern Language

問題文

m 個の相異なるアルファベット var_0, &thinsp;var_1, &thinsp; …&thinsp;, &thinsp;var_{m-1} がある．
0, &thinsp; 1, &thinsp; …&thinsp;, &thinsp; 9, &thinsp; var_0, &thinsp; var_1, &thinsp; …&thinsp;, &thinsp; var_{m-1} の 10+m 種類の文字からなる，長さ N の文字列 s_0s_1s_2…s_{N-1} が与えられる．
この文字列における各アルファベットを数字で置き換えて回文になるようにしたい．(回文とは，前から読んでも後ろから読んでも同じ文字列をあらわす．)
ここで，同じアルファベットは同じ数字で置き換えなければならない．また与えられたすべてのアルファベットvar_iは少なくとも，一度は文字列s_0s_1s_2…s_{N-1}にあらわれる．

アルファベット var_i は 0 以上 u_i 以下の，leading zero を含まない整数に置き換える事ができる．
置き換えた後の文字列が回文になるような置き換え方が何通り存在するかを，mod 10^9+7 で求めよ．
なお，アルファベットの置き換え方が異なれば，得られる文字列が同じでも異なるものとして数える．

入力形式

入力は以下の形式で与えられる

N m
s_0s_1s_2…s_{N-1}
var_0 u_0
...
var_{m-1} u_{m-1}

出力形式

置き換え方の場合の数を 10^9 + 7 で割った剰余を一行で出力せよ．

制約

1 ≤ N ≤ 500

1 ≤ m ≤ 10

0 ≤ u_i ≤ 99

s_i &isin; \{'0', &thinsp; '1', &thinsp; …&thinsp;, &thinsp; '9', &thinsp; var_0, &thinsp; var_1, &thinsp; …&thinsp;, &thinsp; var_{m-1}\}

var_i &isin; \{'a', &thinsp; 'b', &thinsp; …&thinsp;, &thinsp; 'j'\}

各アルファベット var_i は s_0s_1s_2&thinsp;…s_{N-1} に少なくとも一度は現れる．

var_0,&thinsp; var_1,&thinsp; …&thinsp;, &thinsp;var_{m-1} はすべて異なる

入出力例

入力例 1

3 1
a1a
a 99

出力例 1

19

入力例 2

5 3
jbfjb
f 50
b 25
j 5

出力例 2

252

入力例 3

7 3
jag2013
j 53
a 10
g 93

出力例 3

23



Sample input:
3 1
a1a
a 99


Sample output:
19

Submission status: Accepted

Solution code:
#@profile
def dfs(p,s,c,cmin,cmax):
    if len(p) == 0:
        return solve(s,c,cmin,cmax)
    lower, u = p[0]
    c += lower
    if u <= 9:
        cmin[lower] = 0
        cmax[lower] = u
        return dfs(p[1:],s,c,cmin,cmax)
     
    cmin[lower] = 0
    cmax[lower] = 9
    ret = dfs(p[1:],s,c,cmin,cmax)
 
    upper = lower.upper()
    s = s.translate(str.maketrans({lower:upper + lower}))
 
    c += upper
    if u % 10 == 9:
        cmin[upper] = 1
        cmax[upper] = u // 10
        return ret + dfs(p[1:],s,c,cmin,cmax)
    if 20 <= u:
        cmin[upper] = 1
        cmax[upper] = u // 10 - 1
        ret += dfs(p[1:],s,c,cmin,cmax)
    cmin[lower] = 0
    cmax[lower] = u % 10
    cmin[upper] = u // 10
    cmax[upper] = u // 10
    return ret + dfs(p[1:],s,c,cmin,cmax)
#@profile
def solve(s,c,cmin,cmax):
    uf = [-1] * 128
    s1 = map(ord,s[:len(s)//2])
    s2 = map(ord,s[::-1][:len(s)//2])
    for p,q in zip(s1,s2):
        p = root(uf,p)
        q = root(uf,q)
        if p != q:
            if uf[p] >= uf[q]:
                uf[p] += uf[q]
                uf[q] = p
            else:
                uf[q] += uf[p]
                uf[p] = q

    nmin,nmax = {},{}
    for ci in c:
        p = root(uf,ord(ci))
        p = str(p)
        try:
            nmax[p] = min(nmax[p],cmax[ci])
            nmin[p] = max(nmin[p],cmin[ci])
        except KeyError:
            nmax[p] = cmax[ci]
            nmin[p] = cmin[ci]
     
    ret = 1
    for p in nmax.keys():
        if nmax[p] < nmin[p]:
            return 0
        ret *= nmax[p] - nmin[p] + 1
    return ret
    
#@profile 
def root(uf,p):
    if uf[p] < 0:
        return p
    uf[p] = root(uf,uf[p])
    return uf[p]

import sys
f = sys.stdin
 
_, _ = map(int, f.readline().split())
s = f.readline().strip()
p = [line.split() for line in f]
for pi in p:
    pi[1] = int(pi[1])
cmin,cmax = {str(i):i for i in range(10)},{str(i):i for i in range(10)}
characters = '0123456789'
print(dfs(p,s,characters,cmin,cmax) % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
from itertools import product
import sys
readline = sys.stdin.readline
write = sys.stdout.write
def solve():
    MOD = 10**9 + 7
    N, M = map(int, readline().split())
    S = readline().strip()
    U = [0]*M
    L = [0]*M
    mp = {}
    for i in range(10):
        mp[str(i)] = i
    for i in range(M):
        v, u = readline().split()
        mp[v] = i+10
        L[i] = len(u); U[i] = int(u)
    def root(x):
        if prt[x] == x:
            return x
        prt[x] = y = root(prt[x])
        return y
    def unite(x, y):
        px = root(x); py = root(y)
        if px < py:
            prt[py] = px
        else:
            prt[px] = py
    *T, = map(mp.__getitem__, S)
    ans = 0
    t10 = (1,)*10
    for P in product([1, 2], repeat=M):
        ok = 1
        for i in range(M):
            if P[i] > L[i]:
                ok = 0
                break
        if not ok:
            continue

        *prt, = range(10+M*2)
        l = 0; p = P[T[l]-10]-1 if T[l] >= 10 else 0
        r = N-1; q = 0
        while l < r or (l == r and q < p):
            if T[l] >= 10:
                a = T[l]*2-10+p
                if p-1 == -1:
                    l += 1; p = P[T[l]-10]-1 if T[l] >= 10 else 0
                else:
                    p -= 1
            else:
                a = T[l]
                l += 1; p = P[T[l]-10]-1 if T[l] >= 10 else 0
            if T[r] >= 10:
                b = T[r]*2-10+q
                if q+1 == P[T[r]-10]:
                    r -= 1; q = 0
                else:
                    q += 1
            else:
                b = T[r]
                r -= 1; q = 0
            unite(a, b)
        for i in range(10):
            if root(i) != i:
                ok = 0
                break
        if not ok:
            continue

        mi0 = [0]*(10+M*2)
        ma0 = [9]*(10+M*2)

        mi = [0]*(10+M*2); ma = [9]*(10+M*2)
        prt1 = prt[:]
        for Q in product([0, 1], repeat = M):
            mi[:] = mi0; ma[:] = ma0
            ok = 1
            for i in range(M):
                if P[i] < L[i] and Q[i] == 1:
                    ok = 0
                    break
            if not ok:
                continue
            prt[:] = prt1
            for i in range(10):
                mi[i] = ma[i] = i
            for i in range(M):
                if L[i] == 1:
                    v = U[i]
                    e0 = 2*i+10
                    if Q[i]:
                        unite(v, e0)
                    else:
                        ma[e0] = v-1
                else:
                    v1, v0 = divmod(U[i], 10)
                    e0 = 2*i+10; e1 = 2*i+11
                    if Q[i]:
                        unite(v1, e1)
                        ma[e0] = v0
                    else:
                        ma[e0] = 9
                        if P[i] == 2:
                            ma[e1] = v1-1; mi[e1] = 1
            for i in range(10+2*M):
                a = root(i)
                mi[a] = max(mi[a], mi[i])
                ma[a] = min(ma[a], ma[i])
            for i in range(10):
                if root(i) != i or not mi[i] == i == ma[i]:
                    ok = 0
                    break
            if not ok:
                continue

            res = 1
            for i in range(M):
                e0 = 2*i+10; e1 = 2*i+11
                if P[i] == 2:
                    if root(e1) == e1:
                        if not mi[e1] <= ma[e1]:
                            res = 0
                            break
                        res = res * (ma[e1] - mi[e1] + 1) % MOD
                if root(e0) == e0:
                    if not mi[e0] <= ma[e0]:
                        res = 0
                        break
                    res = res * (ma[e0] - mi[e0] + 1) % MOD
            ans += res
    ans %= MOD
    write("%d\n" % ans)
solve()

Submission status: Runtime Error

Solution code:
def dfs(p,s,c,cmin,cmax):
    if len(p) == 0:
        return solve(s,c,cmin,cmax)
    lower, u = p[0]
    c += lower
    if u <= 9:
        cmin[lower] = 0
        cmax[lower] = u
        return dfs(p[1:],s,c,cmin,cmax)
    
    cmin[lower] = 0
    cmax[lower] = 9
    ret = dfs(p[1:],s,c,cmin,cmax)

    upper = lower.upper()
    s = s.translate(str.maketrans({lower:upper + lower}))

    c += upper
    if u % 10 == 9:
        cmin[upper] = 1
        cmax[upper] = u // 10
        return ret + dfs(p[1:],s,c,cmin,cmax)
    if 20 <= u:
        cmin[upper] = 1
        cmax[upper] = u // 10 - 1
        ret += dfs(p[1:],s,c,cmin,cmax)
    cmin[lower] = 0
    cmax[lower] = u % 10
    cmin[upper] = u // 10
    cmax[upper] = u // 10
    return ret + dfs(p[1:],s,c,cmin,cmax)
def solve(s,c,cmin,cmax):
    uf = {ci:-1 for ci in c}
    for i in range(len(s) // 2):
        join(uf,s[i],s[-i-1])
    nmin,nmax = {},{}
    for ci in c:
        p = root(uf,ci)
        try:
            nmax[p] = min(nmax[p],cmax[ci])
            nmin[p] = max(nmin[p],cmin[ci])
        except KeyError:
            nmax[p] = cmax[ci]
            nmin[p] = cmin[ci]
    
    ret = 1
    for p in nmax.keys():
        if nmax[p] < nmin[p]:
            return 0
        ret *= nmax[p] - nmin[p] + 1
    return ret
def join(uf,p,q):
    p = root(uf,p)
    q = root(uf,q)
    if p == q:
        return
    uf[p] += uf[q]
    uf[q] = p
    
def root(uf,p):
    if isinstance(uf[p], int):
        return p
    uf[p] = root(uf,uf[p])
    return uf[p]
import sys
f = sys.stdin

_, _ = map(int, f.readline().split())
s = f.readline().strip()
p = [line.split() for line in f]
for pi in p:
    pi[1] = int(pi[1])
cmin,cmax = {str(i):i for i in range(10)},{str(i):i for i in range(10)}
characters = '0123456789'
print(dfs(p,s,characters,cmin,cmax) % (10 ** 9 + 7))