题解

问题分析

题目要求统计由 ( k ) 个氨基酸的碱基序列（每个氨基酸有多种可选序列）按顺序拼接后，在给定碱基串 ( s ) 中作为连续子串出现的所有方案数。方案差异包括序列选法不同或匹配位置不同，最终结果需对 ( 10^9 + 7 ) 取模。

关键思路

1. 动态规划（DP）状态设计：
   定义 ( dp[i][p] ) 表示处理完前 ( i ) 个氨基酸后，拼接的字符串在 ( s ) 中结束于位置 ( p )（即最后一个字符在 ( s ) 的索引 ( p )）的方案数。

2. 状态转移：
   对于第 ( i ) 个氨基酸的某个可选序列 ( t )（长度为 ( l )），若前 ( i-1 ) 个氨基酸的拼接字符串结束于位置 ( p_{\text{prev}} )，则需满足：

   • ( t ) 与 ( s ) 中从 ( p_{\text{prev}} + 1 ) 开始、长度为 ( l ) 的子串完全匹配；
   • 新的结束位置为 ( p_{\text{curr}} = p_{\text{prev}} + l )。
     此时，( dp[i][p_{\text{curr}}] ) 累加 ( dp[i-1][p_{\text{prev}}] ) 的值。

3. 初始状态：
   前 ( 0 ) 个氨基酸（空串）可视为结束于 ( s ) 中所有可能的“起始前位置”，即 ( p \in {-1, 0, 1, \dots, |s| - 1} )，故 ( dp[0][p] = 1 ) 对所有上述 ( p ) 成立。

4. 高效匹配优化：
   利用滚动哈希（Rabin-Karp 算法）预处理 ( s ) 的前缀哈希，快速计算任意子串的哈希值，从而高效判断 ( t ) 与 ( s ) 的子串是否匹配。

代码实现

MOD = 10**9 + 7

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    k = int(input[ptr])
    ptr += 1
    s = input[ptr]
    ptr += 1
    amino_acids = []
    for _ in range(k):
        a_i = int(input[ptr])
        ptr += 1
        seqs = input[ptr:ptr + a_i]
        ptr += a_i
        amino_acids.append(seqs)
    
    n = len(s)
    if n == 0:
        print(0)
        return
    
    # 预处理哈希：基和模（双哈希减少冲突，此处用单哈希简化）
    base = 911382629
    mod = 10**18 + 3
    prefix_hash = [0] * (n + 1)
    power = [1] * (n + 1)
    for i in range(n):
        prefix_hash[i+1] = (prefix_hash[i] * base + ord(s[i])) % mod
        power[i+1] = (power[i] * base) % mod
    
    # 计算字符串t的哈希
    def get_hash(t):
        h = 0
        for c in t:
            h = (h * base + ord(c)) % mod
        return h
    
    # 初始化DP：dp[i][p+1] 对应结束位置p（p从-1到n-1）
    # dp_prev 是i-1时的状态，用数组存储，索引为p+1（p=-1对应0，p=0对应1，...，p=n-1对应n）
    dp_prev = [0] * (n + 1)
    for p in range(-1, n):
        dp_prev[p + 1] = 1  # p=-1 → 0，p=0→1，...，p=n-1→n
    
    for i in range(k):
        dp_curr = [0] * (n + 1)  # 结束位置p的范围：-1 + sum(l) ... ，但最多n-1
        seqs = amino_acids[i]
        for t in seqs:
            l = len(t)
            if l == 0:
                continue  # 题目中序列应为非空
            if l > n:
                continue  # 长度超过s，无法匹配
            t_hash = get_hash(t)
            # 遍历所有可能的p_prev，使得dp_prev[p_prev + 1] > 0，且p_prev + l < n（即p_prev <= n-1 - l）
            max_p_prev = n - 1 - l
            if max_p_prev < -1:
                continue  # p_prev至少为-1
            # 遍历p_prev从-1到max_p_prev
            for p_prev in range(-1, max_p_prev + 1):
                cnt = dp_prev[p_prev + 1]
                if cnt == 0:
                    continue
                # 计算s[p_prev+1 ... p_prev + l]的哈希
                start = p_prev + 1
                end = start + l
                if end > n:
                    continue
                s_hash = (prefix_hash[end] - prefix_hash[start] * power[end - start]) % mod
                s_hash = (s_hash + mod) % mod  # 确保非负
                if s_hash == t_hash:
                    p_curr = p_prev + l
                    if p_curr >= n:
                        continue
                    dp_curr[p_curr + 1] = (dp_curr[p_curr + 1] + cnt) % MOD
        dp_prev = dp_curr
    
    # 总和所有可能的结束位置
    total = sum(dp_prev) % MOD
    print(total)

if __name__ == "__main__":
    main()

复杂度分析

• 预处理：计算 ( s ) 的前缀哈希和幂数组，时间复杂度 ( O(n) )（( n ) 为 ( s ) 的长度）。
• 动态规划：
  • 共 ( k ) 层，每层处理 ( \sum a_i ) 个序列（( a_i ) 为第 ( i ) 个氨基酸的可选序列数）。
  • 每个序列长度为 ( l ) 时，遍历有效起始位置的时间为 ( O(n) )，哈希匹配为 ( O(1) )。
    总时间复杂度为 ( O(k \cdot \sum a_i \cdot n) )，结合数据范围 ( k \leq 100 )，( \sum a_i \leq 1000 )，( n \leq 10^4 )，可高效运行。

该方法通过动态规划结合哈希优化，准确统计所有合法方案，满足题目要求。