给定一个长度为 $n$ 的，仅包含首 $m$ 个小写字母的字符串 $S$。
计算存在多少个不同的长度为 $n$ 的，只包含首 $m$ 个字母的字符串 $T$，满足 $S$ 和 $T$ 的最长公共子序列 (LCS) 的长度是 $n-1$。
第一行包含两个正整数 $n, m$ ($n \leq 10^5, 2 \leq m \leq 26$)，表示 $S, T$ 的长度和字符集的大小。
接下来一行包含字符串 $S$。
输出一行一个整数，表示满足条件的 $T$ 的个数。
这道题方法很多。下面将一种基于 DP 的做法。
我们知道，根据经典的 $O(n^2)$ DP，LCS 的转移是根据对应位置上的字符是否相同分两种情况转移的。即 $f_{i, j}$ 只与 $f_{i-1, j}, f_{i, j-1}$ 以及 $f_{i-1, j-1}$ 有关。
但是我们有 $f_{n, n} = n-1$，这样以来，对于所有满足 $|i-j| \leq 1$ 的 $(i, j)$，均有 $\min \{i, j\} - 1 \leq f_{i, j} \leq \min \{i, j\}$。
因此，我们只关心对于 $|i-j| \leq 1$ 的 $(i, j)$，即 $f_{i, i-1}, f_{i, i}, f_{i, i+1}$，由于每个 DP 值只有两种情况，因此一共至多只有 $8$ 种情况，我们可以将它状压为状态 $A$。(注：$f_{i, j}$ 表示 $T$ 的 $i-$前缀和 $S$ 的 $i-$前缀的 LCS 的长度)。
记 $g_{i, A}$ 表示有多少个 $T$ 的 $i-$前缀，满足上述三个 DP 值的状态为 $A$，很容易预处理出初始状态。考虑转移，即 $T$ 中加入第 $i+1$ 个字符串。那么，显然枚举 $m$ 个字符，然后分别和 $s_i, s_{i+1}, s_{i+2}$ (如果 $s$ 以 $1$ 编号) 比较，然后根据上述两种方式转移，得到新的状态 $A'$，即可向 $g_{i+1, A'}$ 转移。
最后由于只要求 $f_{n, n} = n-1$，而其它的我们无需关心 (即怎么样都可以)，因此把满足条件的 $4$ 种状态的总数加起来就可以了。(这题其实不用取模，因为实际的答案不会很大)
#include <bits/stdc++.h>
#define N 100034
using namespace std;
typedef char state;
typedef long long ll;
int n, m;
char s[N];
ll f[N][8];
int main(){
int i, j, k; state p;
int q[3], nq[3];
scanf("%d%d%s", &n, &m, s + 1);
for(i = 1; i <= n; ++i) s[i] &= 31;
for(i = 1; i <= m; ++i){
p = 1; // lcs[1][0] = 1
if(i == s[1]) p |= 2; // lcs[1][1] = 1
if(i == s[1] || i == s[2]) p |= 4; // lcs[1][2] = 1;
++f[1][p];
}
for(i = 1; i < n; ++i)
for(j = 0; j < 8; ++j)
if(f[i][j]){
q[0] = i - 2 + (j & 1);
q[1] = i - 1 + (j >> 1 & 1);
q[2] = i - 1 + (j >> 2 & 1);
for(k = 1; k <= m; ++k){
nq[0] = (k == s[i] ? q[0] + 1 : q[1]);
nq[1] = (k == s[i + 1] ? q[1] + 1 : max(nq[0], q[2]));
nq[2] = (k == s[i + 2] ? q[2] + 1 : nq[1]);
if(nq[0] < i - 1 || nq[1] < i || nq[2] < i) continue;
p = nq[0] - (i - 1);
p |= (nq[1] - i) << 1;
p |= (nq[2] - i) << 2;
f[i + 1][p] += f[i][j];
}
}
printf("%lld\n", f[n][0] + f[n][1] + f[n][4] + f[n][5]);
return 0;
}
坑1：注意 LCS 的转移方式，对应位置上字符不相等时，应该是 $f_{i, j} = \max \{f_{i-1, j}, f_{i, j-1}\}$。