Problem:


問題名 DNA

遺伝子は、A, T, G, C からなる文字列です。
この世界の遺伝子は奇妙なことに、ある構文規則に従うことが知られています。

構文規則は、次のような形で与えられます。

非終端記号1: 記号1_1 記号1_2 ... 記号1_n1
非終端記号2: 記号2_1 記号2_2 ... 記号2_n2
...
非終端記号m: 記号m_1 記号m_2 ... 記号m_nm

記号は非終端記号または終端記号のどちらかです。
非終端記号は小文字文字列で表され、終端記号はA, T, G, Cのうちのいくつかの文字が、"["と"]"に囲まれた文字列で表されます。

構文規則の例は次のようになります。

dna: a a b b
a: [AT]
b: [GC]

"非終端記号i: 記号i_1 記号i_2 ... 記号i_ni" を非終端記号 i のルールと呼び、ルールは、構文規則に現れる各非終端記号に対して、ちょうど 1 つづつ存在します。

文字列 s が非終端記号 i に「マッチする」とは、 s = s1 + s2 + ... + sni となるような s の部分文字列 {sj} が存在し、sj (1 ≤ j ≤ ni)がルール内の記号 j にマッチすることをいいます。

文字列 s が終端記号に「マッチする」とは、文字列が 1 文字からなり、その文字が終端記号を表す文字列に含まれることをいいます。

文字列が構文規則に従うとは、非終端記号 1 にその文字列がマッチすることをいいます。

ルール i は、記号のうちに、非終端記号 j (j ≤ i) を含みません。

構文規則と、4つの整数 Na , Nt, Ng, Nc が与えられます。
構文規則に従い、A をちょうど Na 個、T をちょうど Nt 個、G をちょうど Ng 個、C をちょうど Nc 個含むような遺伝子の総数を 1,000,000,007 で割った余りを求めなさい。

Input

Na Nt Ng Nc
m
非終端記号1: 記号 11 記号 12 ... 記号 1n1
非終端記号2: 記号 21 記号 22 ... 記号 2n2
...
非終端記号 m: 記号 m1 記号 m2 ... 記号 mnm

0 ≤ Na, Nt, Ng, Nc ≤ 50

1 ≤ m ≤ 50

1 ≤ ni ≤ 10

1 ≤  記号を表す文字列の長さ  ≤ 20 (※記号にマッチする文字列の長さではないことに注意)

Output

総数を 1,000,000,007 で割った余り

Sample Input 1

1 0 1 0
3
dna: a b
a: [AT]
b: [GC]

Output for the Sample Input 1

1

"AG"の一つです。

Sample Input 2

1 1 1 2
1
k: [ATG] [ATG] [ATG] [C] [C]

Output for the Sample Input 2

6

"ATGCC", "AGTCC", "TAGCC", "TGACC", "GATCC", "GTACC"の6つです。

Sample Input 3

3 1 1 1
3
inv: at b b b
at: [ATG] b
b: [C]

Output for the Sample Input 3

0



Sample input:
1 0 1 0
3
dna: a b
a: [AT]
b: [GC]


Sample output:
1

Submission status: Time Limit Exceeded

Solution code:
table= {}
def solve(dict,key):
    global table
    if key in table:
        return table[key]
    ret = []
    for i in dict[key]:
        if i[0] == '[':
            ret.append(i[1:-1])
        else:
            ret += (solve(dict, i))
    if len(ret) > 200:
        for i in table.keys():
            table[i]=''
            return ''
    table[key] = ret
    return ret

Na, Nt, Ng, Nc = [int(i) for i in input().split()]
m = int(input())

dict = {}

for i in range(m):
    key, value = [i for i in input().split(': ')]
    if i == 0:
        aa = key
    value = value.split()
    dict[key] = value

lis = solve(dict, aa)
if len(lis)==Na+Nt+Ng+Nc:
    DP = [[[[0 for i in range(Nc+1)] for j in range(Ng+1)]for k in range(Nt+1)]for l in range(Na+1)]
    DP[0][0][0][0] = 1
    for i in range(len(lis)):
        hA=hT=hG=hC=False
        #print(i)
        for char in lis[i]:
            if char == 'A':
                hA = True
            elif char == 'G':
                hG  = True
            elif char == 'T':
                hT = True
            else:
                hC = True
        for a in range(i+1):
            if a > Na:
                break
            for t in range(i-a+1):
                if t > Nt:
                    break
                for g in range(i-a-t+1):
                    if g > Ng:
                        break
                    c = i-a-t-g
                    if c > Nc:
                        continue
                    ans = DP[a][t][g][c] % 1000000007
                    if hA and a+1 <= Na:
                        DP[a+1][t][g][c] += ans
                    if hT and t+1 <= Nt:
                        DP[a][t+1][g][c] += ans
                    if hG and g+1 <=  Ng:
                        DP[a][t][g+1][c] += ans
                    if hC and c+1 <= Nc:
                        DP[a][t][g][c+1] += ans
        #DPC = DPN
        #DPN = [[[0 for j in range(Ng+1)]for k in range(Nt+1)]for l in range(Na+1)]
    print(DP[Na][Nt][Ng][Nc]%1000000007)
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
table= {}
def solve(dict,key):
    global table
    if key in table:
        return table[key]
    ret = []
    for i in dict[key]:
        if i[0] == '[':
            ret.append(i[1:-1])
        else:
            ret += (solve(dict, i))
    if len(ret) > 200:
        for i in table.keys():
            table[i]=''
            return ''
    table[key] = ret
    return ret

Na, Nt, Ng, Nc = [int(i) for i in input().split()]
m = int(input())

dict = {}

for i in range(m):
    key, value = [i for i in input().split(': ')]
    if i == 0:
        aa = key
    value = value.split()
    dict[key] = value

lis = solve(dict, aa)
if len(lis)==Na+Nt+Ng+Nc:
    current =0
    next = 1
    DP = [[[[0 for i in range(2)] for j in range(Ng+1)]for k in range(Nt+1)]for l in range(Na+1)]
    DP[0][0][0][0] = 1
    for i in range(len(lis)):
        hA=hT=hG=hC=False
        #print(i)
        for char in lis[i]:
            if char == 'A':
                hA = True
            elif char == 'G':
                hG  = True
            elif char == 'T':
                hT = True
            else:
                hC = True
        for a in range(i+1):
            if a > Na:
                break
            for t in range(i-a+1):
                if t > Nt:
                    break
                for g in range(i-a-t+1):
                    if g > Ng:
                        break
                    c = i-a-t-g
                    if c > Nc:
                        continue
                    ans = DP[a][t][g][current] % 1000000007
                    if hA and a+1 <= Na:
                        DP[a+1][t][g][next] += ans
                    if hT and t+1 <= Nt:
                        DP[a][t+1][g][next] += ans
                    if hG and g+1 <=  Ng:
                        DP[a][t][g+1][next] += ans
                    if hC and c+1 <= Nc:
                        DP[a][t][g][next] += ans
        #DPC = DPN
        N=current
        current = next
        next = N
        for i in range(Na+1):
            for j in range(Nt+1):
                for k in range(Ng+1):
                    DP[i][j][k][next] = 0
    print(DP[Na][Nt][Ng][current]%1000000007)
else:
    print(0)

Submission status: Memory Limit Exceeded

Solution code:
def solve(dict,key):
    ret = []
    for i in dict[key]:
        if i[0] == '[':
            ret.append(i[1:-1])
        else:
            ret += (solve(dict, i))
    return ret

def count(lis,index,a,t,g,c,a_,t_,g_,c_):
    if a_ > a or t_ > t or c_ > c or g_ > g:
    #    print(a,a_,t,t_,g,g_,c,c_,'  ',lis[index-1])
        return 0
    if index == len(lis):
#        print(a_,t_,g_,c_)
        return 1
    ret = 0
#    print(index)
#    print(a,a_,t,t_,g,g_,c,c_)
    for i in lis[index]:
#        print(i)
        if i =='A':
            ret += count(lis,index + 1,a,t,g,c,a_+1,t_,g_,c_)
        elif i =='T':
            ret += count(lis,index + 1,a,t,g,c,a_,t_+1,g_,c_)
        elif i =='C':
            ret += count(lis,index + 1,a,t,g,c,a_,t_,g_,c_+1)
        elif i == 'G':
            ret += count(lis,index + 1,a,t,g,c,a_,t_,g_+1,c_)
    return ret
    
Na, Nt, Ng, Nc = [int(i) for i in input().split()]
m = int(input())

dict = {}

for i in range(m):
    key, value = [i for i in input().split(': ')]
    if i == 0:
        aa = key
    value = value.split()
    dict[key] = value

lis = solve(dict, aa)
#print(lis)
if len(lis)==Na+Nt+Ng+Nc:
    print(count(lis,0,Na,Nt,Ng,Nc,0,0,0,0))
else:
    print(0)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
def solve():
    readline = sys.stdin.readline
    write = sys.stdout.write
    MOD = 10**9 + 7
    Na, Nt, Ng, Nc = map(int, readline().split())
    L = Na + Nt + Ng + Nc
    M = int(readline())
    MP = {}
    S = []
    for i in range(M):
        s = readline().strip()
        s1, s2 = s.split(": ")
        MP[s1] = s2.split(" ")
        S.append(s1)
    R = []
    memo = {}
    def dfs(s):
        if s in memo:
            return memo[s]
        r = []
        for e in MP[s]:
            if e[0] == "[":
                w = 0
                for v in map("ATGC".index, e[1:-1]):
                    w |= 1 << v
                r.append(w)
            else:
                r0 = dfs(e)
                if r0 is None:
                    return None
                r.extend(r0)
        if len(r) > L:
            return None
        memo[s] = r
        return r
    res = dfs(S[0])
    if res is None or len(res) < L:
        write("0\n")
        return
    L = len(res)

    T = [defaultdict(int) for i in range(L+1)]
    T[0][Na, Nt, Ng, Nc] = 1
    for k in range(L):
        s = res[k]
        p0 = s & 1; p1 = s & 2; p2 = s & 4; p3 = s & 8
        T1 = T[k+1]
        for (a, b, c, d), v in T[k].items():
            v %= MOD
            if p0 and a:
                T1[a-1, b, c, d] += v
            if p1 and b:
                T1[a, b-1, c, d] += v
            if p2 and c:
                T1[a, b, c-1, d] += v
            if p3 and d:
                T1[a, b, c, d-1] += v
    write("%d\n" % (T[L][0, 0, 0, 0] % MOD))
solve()

Submission status: Runtime Error

Solution code:
table= {}
def solve(dict,key):
    global table
    if key in table:
    #    print('key=',key)
        return table[key]
    ret = []
    #print(key)
    for i in dict[key]:
        if i[0] == '[':
            ret.append(i[1:-1])
        else:
            ret += (solve(dict, i))
    if len(ret) > 200:
        for i in table.keys():
            table[i]=''
            return ''
    table[key] = ret
    #print(key)
    return ret

Na, Nt, Ng, Nc = [int(i) for i in input().split()]
m = int(input())

dict = {}

for i in range(m):
    key, value = [i for i in input().split(': ')]
    if i == 0:
        aa = key
    value = value.split()
    dict[key] = value

lis = solve(dict, aa)
if len(lis)==Na+Nt+Ng+Nc:
    DP = [[[[0 for i in range(Nc+1)]for j in range(Ng+1)]for k in range(N+1)]for l in range(len(lis)+1)]
    #print(DP[4])
    DP[0][0][0][0] = 1 
    #print(DP)
    for i in range(len(lis)):
        str = lis[i]
        for a in range(i+1):
            if a > Na:
                break
            for t in range(i-a+1):
                if t > Nt:
                    break
                for g in range(i-a-t+1):
                    if g > Ng:
                        break
#                    print(i,a,t,g)
                    if i-a-t-g > Nc:
                        continue
                    ans = DP[a][t][g][c] % 1000000007
 #                   print(ans)
                    for char in str:
#                        print(i,a,t,g)
                        if char == 'A':
                            if a+1 > Na:
                                continue
                            DP[a+1][t][g][c] += ans
                        elif char == 'T':
                            if t+1 > Nt:
                                continue
                            DP[a][t+1][g][c] += ans
                        elif char == 'G':
                            if g+1 > Ng:
                                continue
                            DP[a][t][g+1][c] += ans
                        elif char == 'C':
                            if i-a-t-g+1> Nc:
                                continue
                            DP[a][t][g][c+1] += ans
#                        print(DP)
                    #DP[i][a][t][g] = ans % 1000000007

    print(DP[len(lis)][Na][Nt][Ng]%1000000007)
else:
    print(0)