P2516 [HAOI2010] 最长公共子序列

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 5e3 + 10, mod = 1e8;
int n, m, k;
char ch, a[maxn], b[maxn];
ll f[2][maxn], g[2][maxn];

int main()
{
    for (int i = 1; (ch = getchar()) != '.'; a[i] = ch, n = i, i++) ;
    getchar();
    for (int i = 1; (ch = getchar()) != '.'; b[i] = ch, m = i, i++) ;
    for (int i = 0; i <= m; i++) g[0][i] = 1; g[1][0] = 1;
    for (int i = 1; i <= n; i++, k ^= 1)
    {
        for (int j = 1; j <= m; j++)
        {
            g[k ^ 1][j] = 0;
            f[k ^ 1][j] = (a[i] == b[j]) ? f[k][j - 1] + 1 : max(f[k][j], f[k ^ 1][j - 1]);
            if (a[i] == b[j]) g[k ^ 1][j] += g[k][j - 1];
            if (f[k ^ 1][j] == f[k ^ 1][j - 1]) g[k ^ 1][j] += g[k ^ 1][j - 1];
            if (f[k ^ 1][j] == f[k][j]) g[k ^ 1][j] += g[k][j];
            if (f[k ^ 1][j] == f[k][j - 1]) g[k ^ 1][j] -= g[k][j - 1];
            g[k ^ 1][j] %= mod;
        }
    }
    printf("%lld\n%lld\n", f[k][m], g[k][m]);
    return 0;
}