题解

问题分析

题目要求统计长度为 ( N ) 的合法兑奖串（不含子串 "NOI"）中，与给定长度为 ( K ) 的奖章串的最长公共子序列（LCS）长度分别为 ( 0, 1, \dots, K ) 的数量。核心挑战在于同时处理 LCS 长度计算 和 避免 "NOI" 子串 两个约束，需通过动态规划（DP）结合状态压缩高效求解。

关键思路

1. 动态规划状态设计：
   需跟踪三个核心信息：

   • 当前兑奖串长度 ( i )（从 ( 0 ) 到 ( N )）。
   • 最后两个字符（prev, curr），用于检查是否形成 "NOI" 子串。
   • LCS 状态：用一个数组表示兑奖串前 ( i ) 个字符与奖章串前 ( j ) 个字符的 LCS 长度（( j = 1, 2, \dots, K )），通过编码压缩为整数。

2. 状态转移：
   对于每个状态，尝试添加新字符（N, O, I 分别映射为 ( 0, 1, 2 )），检查是否形成 "NOI" 子串（若形成则跳过），并更新 LCS 状态。LCS 状态的更新遵循经典 LCS 递推规则：

   • 新字符与奖章串第 ( j ) 个字符匹配时，LCS 长度可能增加 ( 1 )；
   • 否则，取前序状态的最大值。

3. 结果统计：
   当兑奖串长度达到 ( N ) 时，根据 LCS 状态的最终值（即与奖章串的 LCS 长度）汇总计数。

代码实现

MOD = 10**9 + 7

def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    K = int(input[ptr])
    ptr += 1
    A = input[ptr]
    ptr += 1
    # 映射字符为0:N, 1:O, 2:I
    char_to_idx = {'N':0, 'O':1, 'I':2}
    A = [char_to_idx[c] for c in A]
    
    # 编码和解码LCS状态（s_list是[s1, s2, ..., sK]）
    def encode(s_list):
        code = 0
        for s in s_list:
            code = code * 16 + s  # 每个s_j最多15（K<=15），用4位足够
        return code
    
    def decode(code, K):
        s_list = []
        for _ in range(K):
            s_list.append(code % 16)
            code = code // 16
        s_list.reverse()  # 恢复s1到sK的顺序
        return s_list
    
    # 初始化DP：current_dp的键是( (prev, curr), s_code )，值是计数
    current_dp = defaultdict(int)
    initial_lt = (-1, -1)  # 初始状态：无字符
    initial_s_list = [0]*K
    initial_s_code = encode(initial_s_list)
    current_dp[(initial_lt, initial_s_code)] = 1
    
    for i in range(N):
        next_dp = defaultdict(int)
        for (lt, s_code), cnt in current_dp.items():
            prev, curr = lt
            # 尝试添加新字符c（0:N,1:O,2:I）
            for c in [0, 1, 2]:
                # 检查是否形成"NOI"子串（仅当当前长度>=2时可能）
                if i >= 2:  # 添加后长度为i+1 >=3
                    if prev == 0 and curr == 1 and c == 2:
                        continue  # 非法，跳过
                
                # 计算新的last_two (new_prev, new_curr)
                if i == 0:
                    new_prev = -1
                    new_curr = c
                elif i == 1:
                    new_prev = curr  # 之前的curr是第一个字符
                    new_curr = c
                else:
                    new_prev = curr
                    new_curr = c
                new_lt = (new_prev, new_curr)
                
                # 解码当前s_code得到s_list [s1, s2, ..., sK]
                s_list = decode(s_code, K)
                
                # 计算新的s_prime_list [s'1, s'2, ..., s'K]
                s_prime = [0]*(K+1)  # s_prime[0] = 0（辅助）
                for j in range(1, K+1):
                    # s[j] = s_list[j-1]
                    # s[j-1] = s_list[j-2]（j>=2），否则为0
                    s_j = s_list[j-1] if j-1 < len(s_list) else 0
                    s_j_prev = s_list[j-2] if j-2 >=0 else 0
                    # 递推公式
                    s_prime[j] = max(s_j, s_prime[j-1])
                    if c == A[j-1]:
                        s_prime[j] = max(s_prime[j], s_j_prev + 1)
                s_prime_list = s_prime[1:]  # 取s'1到s'K
                s_prime_code = encode(s_prime_list)
                
                # 更新next_dp
                next_dp[(new_lt, s_prime_code)] = (next_dp[(new_lt, s_prime_code)] + cnt) % MOD
        
        current_dp = next_dp
    
    # 统计结果：按LCS长度（s_list[-1]）汇总
    result = [0]*(K+1)
    for (lt, s_code), cnt in current_dp.items():
        s_list = decode(s_code, K)
        lcs_len = s_list[-1] if K > 0 else 0
        if 0 <= lcs_len <= K:
            result[lcs_len] = (result[lcs_len] + cnt) % MOD
    
    for num in result:
        print(num)

if __name__ == "__main__":
    main()

复杂度分析

• 状态数：兑奖串长度 ( N \leq 1000 )，最后两个字符的状态共 ( 13 ) 种（含初始状态），LCS 状态数因 ( K \leq 15 ) 且受单调性约束，实际约为 ( 10^5 ) 量级。总状态数约为 ( 1000 \times 13 \times 10^5 = 1.3 \times 10^9 )，但通过字典存储仅保留非零计数状态，实际可高效处理。
• 转移：每个状态尝试 ( 3 ) 个新字符，每次转移涉及 LCS 状态的解码、计算和编码，时间复杂度为 ( O(N \times 13 \times S \times K) )（( S ) 为 LCS 状态数），可满足 ( N \leq 1000, K \leq 15 ) 的数据范围。

该方法通过状态压缩和动态规划，高效平衡了约束条件与计数需求，成功解决问题。