专栏文章

题解：AT_abc391_g [ABC391G] Many LCS

SSunburstFan
AT_abc391_g题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipzkbxe
此快照首次捕获于
2025/12/03 20:31
3 个月前
此快照最后确认于
2025/12/03 20:31
3 个月前
查看原文

[ABC391G] Many LCS

题目大意

有一个长度为 NN 的小写英文字符串 SS。需要统计对于所有可能的长度为 MM 的小写英文字符串 TT，它们与 SS 的最长公共子序列长度为 0,1,2,…,N0,1,2,\dots,N 各自为多少。

解题思路

dp of dp，之前并没有做过这类的题目。
回忆计算 LCS⁡\operatorname{LCS} 的过程，注意到状态转移数组 f 的差分数组只由 0 和 1 组成。
对原串 SS 的状态进行位压缩，以二进制表示子序列选取情况。
对每个状态 SS 和待加入的字母 xx，使用一个转移函数求出新状态。DP 里再根据已经转移到的子序列与生成的字母数位置，累加结果。
时间复杂度 O(26×(n+m)×2n)O(26 \times (n + m) \times 2^n)。
这里给出核心代码：
CPP
for(int i=1;i<=n;i++){
        a[i]=s[i-1]-'a';
    }
    for(int S=0;S<(1<<n);S++){
        for(int i=0;i<26;i++){
            nxt[S][i]=calc(S,i);
        }
    }

    f[0][0]=1;
    for(int i=0;i<m;i++){
        for(int S=0;S<(1<<n);S++){
            for(int j=0;j<26;j++){
                f[nxt[S][j]][i+1]=(f[nxt[S][j]][i+1]+f[S][i])%mod;
            }
        }
    }
calc 部分略。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...