题解：AT_abc391_g [ABC391G] Many LCS

· · 题解

[ABC391G] Many LCS

题目大意

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

解题思路

dp of dp，之前并没有做过这类的题目。

回忆计算 \operatorname{LCS} 的过程，注意到状态转移数组 f 的差分数组只由 0 和 1 组成。

对原串 S 的状态进行位压缩，以二进制表示子序列选取情况。

对每个状态 S 和待加入的字母 x，使用一个转移函数求出新状态。DP 里再根据已经转移到的子序列与生成的字母数位置，累加结果。

时间复杂度 O(26 \times (n + m) \times 2^n)。

这里给出核心代码：

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 部分略。