P2516 [HAOI2010]最长公共子序列

问题分析

在最长公共子序列问题的基础上，本题要求输出最长公共子序列（后文简称LCS）的个数。

难点：尽管LCS长度固定，LCS不一定只有一种。

要找到LCS的个数，我们可以从转移的过程入手。
若以$d(i, j)$表示序列$A$从$1$到$i$，序列$B$从$1$到$j$的LCS长度，那么$d(i, j)$可能有以下三种转移方式：

• $d(i, j) = d(i - 1, j - 1) + 1, a_i = b_j$
• $d(i, j) = d(i - 1, j)$
• $d(i, j) = d(i, j - 1)$

可以发现，要求长度为$d(i, j)$的LCS的个数，只需要知道长度为$d(i, j)$转移来源的LCS的个数，我们就可以推出最终的答案。

因此，如果用$num(i, j)$表示长度为$d(i, j)$的LCS的个数，$num(i, j)$就可以如此转移：

• 若从$d(i - 1, j - 1)$转移：$num(i, j) = num(i, j) + num(i - 1, j - 1), a_i = b_j$
• 若从$d(i - 1, j)$转移：$num(i, j) = num(i, j) + num(i - 1, j)$
• 若从$d(i, j - 1)$转移：$num(i, j) = num(i, j) + num(i, j - 1)$

特殊情况：如果$d(i - 1, j)$和$d(i, j - 1)$都从$d(i - 1, j - 1)$转移，即$a_i \neq b_j \land d(i, j) = d(i - 1, j - 1)$，就多加了一次，应当减去，即：

• $num(i, j) = num(i, j) - num(i - 1, j - 1), a_i \neq b_j \land d(i, j) = d(i - 1, j - 1)$

细节问题

• 内存限制125MB,若使用int d[5005][5005]和int num[5005][5005]开二维数组，空间约为191MB，需要使用滚动数组压缩空间。
• 取模应当每步取模，但本题数据并没有卡这个地方。如果卡了这个地方，一般开long long可以过。
• 如果使用std::string作为字符串容器，数组d[t][j]和num[t][j]仍要从1开始，否则会出现越界问题。

代码实现

#include <iostream>

const int N = 5005, MOD = 1e8;

int la, lb, d[2][N], num[2][N], t = 0;
std::string a, b;

int main()
{
    std::cin >> a >> b;
    la = a.length(), lb = b.length();
    la--, lb--;

    for (int i = 0; i <= lb; i++)
        num[0][i] = 1;
    num[1][0] = 1;

    for (int i = 1; i <= la; i++, t ^= 1)
    {
        for (int j = 1; j <= lb; j++)
        {
            num[t ^ 1][j] = 0;
            if (a[i - 1] == b[j - 1])
            {
                d[t ^ 1][j] = d[t][j - 1] + 1;
                num[t ^ 1][j] += num[t][j - 1];
            }
            else
            {
                d[t ^ 1][j] = std::max(d[t][j], d[t ^ 1][j - 1]);
            }

            if (d[t ^ 1][j] == d[t ^ 1][j - 1])
            {
                num[t ^ 1][j] += num[t ^ 1][j - 1];
            }
            if (d[t ^ 1][j] == d[t][j])
            {
                num[t ^ 1][j] += num[t][j];
            }
            if (a[i - 1] != b[j - 1] && d[t ^ 1][j] == d[t][j - 1])
            {
                num[t ^ 1][j] -= num[t][j - 1];
            }
            num[t ^ 1][j] = num[t ^ 1][j] % MOD;
        }
    }

    std::cout << d[t][lb] << std::endl
              << (num[t][lb] + MOD) % MOD << std::endl;
    return 0;
}