Subtask 1: ~m, n \leq 20~

Đáp án của bài toán đơn giản chỉ là số dãy con chung (phân biệt) của ~a~ và ~b~, ta quay lui nhị phân mọi dãy con của ~a~ và kiểm tra liệu nó có phải dãy con của ~b~ hay không, lấy dãy dài nhất và số lượng.

Subtask 4: các số trong ~a~ phân biệt, các số trong ~b~ phân biệt

Đáp án của bài toán đơn giản chỉ là số dãy con chung (không cần phân biệt) của ~a~ và ~b~. Ta quy hoạch động để tính đáp án cho bài toán này (Có thể làm tương tự thuật toán LCS hoặc sắp xếp dãy ~b~ theo dãy ~a~ rồi thực hiện đếm số dãy con tăng dài nhất).

Subtask 2: ~m, n \leq 500~

Gọi ~lcs_{i,j}~ =đĐộ dài dãy con chung dài nhất có thể tạo từ ~a[1 \cdots i]~ và ~b[1 \cdots j]~, trong đó dãy phải kết thúc bởi ~b_j~.

Gọi ~f_{i, j}~ = số dãy ~lcs_{i,j}~ khác nhau tạo được.

Việc tính toán mảng ~lcs~ đã rất quen thuộc, ta bàn cách tính mảng ~f~.

Ta có thể thêm ~a_0~ vào mọi dãy ~c~, khi đó: ~f_{i, 0} = 1~.

Chú ý: nếu tồn tại một số ~t < j~ mà ~b_t = b_j~ và ~lcs_{i, j} = lcs_{i, t}~ , ~f_{i,j}~ cũng chứa cả các dãy trong ~f_{i,t}~.

Lúc này:

• Nếu ~a_i = b_j~ :
  • ~f_{i,j} = ∑ f_{i - 1,t}~ với mọi ~0 \leq t < j~ và ~lcs_{i,j} = lcs_{i - 1, t} + 1~, ~b_h \neq b_t \forall h \in [t + 1, j - 1]~

• Nếu ~a_i \neq b_j~ :
  • ~f_{i, j} = f_{i - 1, j}~

Từ đây ta có thuật toán O(~n^3~).

Subtask 3: ~m, n \leq 2000~

Ý tưởng giống như trên, ta có thể sử dụng một cây segment tree để cập nhật nhanh và truy vấn nhanh tổng giá trị ~f_{i - 1,t}~ để có được thuật toán O(~n^2logn~).

Subtask 5: Không có giới hạn gì thêm

Trong trường hợp này, ta sẽ sử dụng tổng tiền tố.

Với các vị trí mà giá trị ~b~ bằng nhau, tức là các vị trí ~j_1~ , ~j_2~ , ~\cdots~, ~j_k~ mà ~b_{j_1} = b_{j_2} = \cdots = b_{j_k}~ , thay vì lưu lại ~f_{i, j_1}~ , ~f_{i, j_2}~ , ~\cdots~ , ~f_{i, j_k}~ ; ta lưu lại ~g_{i, j_1} = f_{i, j_1}~ , ~g_{i, j_2} = f_{i, j_2} - f_{i, j_1}~ , ~\cdots~ , ~g_{i, j_k} = f_{i,j_k} - f_{i, {j_k - 1}}~.

Khi đó: ~f_{i,j} = \sum_{t = 0} ^ {j - 1} g_{i - 1, t}~ , cho ta một thuật toán có độ phức tạp O(~n^2~).

Khi code các bạn nhớ cẩn thận xử lý để không bị MLE nhé.

Hoặc có một cách khác là:

Gọi ~dp_{i, j}~ = độ dài dãy con chung dài nhất có thể tạo từ ~a[1 \cdots i]~ và ~b[1 \cdots j]~.

Gọi ~way_{i, j}~ = số lượng dãy con chung có độ dài ~dp_{i, j}~.

Công thức truy hồi:

• Nếu ~a_i = b_j~ :
  • ~dp_{i, j} = dp_{i - 1, j - 1} + 1~
  • ~f_{i, j} = f_{i - 1, j - 1}~
• Nếu ~a_i \neq b_j~, khi này xảy ra 3 trường hợp:
  • Nếu ~dp_{i - 1, j} = dp_{i, j - 1}~, ta đơn giản lấy:
    • ~dp_{i, j} = dp_{i - 1, j}~
    • ~f_{i, j} = f_{i, j - 1} + f_{i - 1, j}~, ở đây có thể sẽ bị lấy dư nếu ~dp_{i - 1, j - 1} = dp_{i, j}~, khi này ta phải trừ thêm ~f_{i - 1, j - 1}~.
  • Ngược lại nếu ~dp_{i - 1, j} \neq dp_{i, j - 1}~, thì đơn giản, ta sẽ lấy ở bên có lcs lớn hơn:
    • ~dp_{i - 1, j} > dp_{i, j - 1}~:
      • ~dp_{i, j} = dp_{i - 1, j}~
      • ~f_{i, j} = f_{i - 1, j}~
    • ~dp_{i - 1, j} < dp_{i, j - 1}~:
      • ~dp_{i, j} = dp_{i, j - 1}~
      • ~f_{i, j} = f_{i, j - 1}~

Code mẫu

#include <bits/stdc++.h>

using namespace std;

#define all(a) a.begin(), a.end()

const int MAX_N = 1e4 + 5;
const int mod = 123456789;

void add(int& a, const int& b) {
    a += b;
    if (a >= mod) {
        a -= mod;
    }
}

int n, m;
int a[MAX_N], b[MAX_N];
int p[MAX_N];
int lcs[2][MAX_N];
int f[2][MAX_N];
vector<int> ns;
vector<int> pos[MAX_N << 1];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("lcs.inp", "r", stdin);
    freopen("lcs.out", "w", stdout);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        ns.push_back(a[i]);
    }
    for (int i = 1; i <= m; i++) {
        cin >> b[i];
        ns.push_back(b[i]);
    }

    sort(all(ns));
    ns.erase(unique(all(ns)), ns.end());

    for (int i = 1; i <= n; i++) {
        a[i] = lower_bound(all(ns), a[i]) - ns.begin() + 1;
    }
    for (int i = 1; i <= m; i++) {
        b[i] = lower_bound(all(ns), b[i]) - ns.begin() + 1;
        pos[b[i]].push_back(i);
    }

    bool prev = 0, now = 1;
    f[prev][0] = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            p[b[j]] = -1;
        }

        int mxLcs = 0, cntLcs = 0;

        for (int j = 0; j <= m; j++) {
            if (a[i] == b[j]) {
                lcs[now][j] = mxLcs;
                f[now][j] = cntLcs;
            }
            else {
                lcs[now][j] = lcs[prev][j];
                f[now][j] = f[prev][j];
            }

            if (lcs[prev][j] + 1 > mxLcs) {
                mxLcs = lcs[prev][j] + 1;
                cntLcs = f[prev][j];
            }
            else {
                if (lcs[prev][j] + 1 == mxLcs) {
                    add(cntLcs, f[prev][j]);

                    if (p[b[j]] >= 0) {
                        if (lcs[prev][pos[b[j]][p[b[j]]]] + 1 == mxLcs) {
                            add(cntLcs, mod - f[prev][pos[b[j]][p[b[j]]]]);
                        }
                    }
                }
            }

            p[b[j]]++;
        }

        swap(prev, now);
    }

    int mxLcs = *max_element(lcs[prev], lcs[prev] + m + 1);
    int cntLcs = 0;
    for (int i = m; ~i; i--) {
        if (p[b[i]] == -2) continue;
        p[b[i]] = -2;
        if (lcs[prev][i] == mxLcs) {
            add(cntLcs, f[prev][i]);
        }
    }

    cout << mxLcs << " " << cntLcs;

    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e4 + 5;
const int mod = 123456789;

void add(int& a, const int& b) {
    a += b;
    if (a >= mod) {
        a -= mod;
    }
}

int n, m;
int a[MAX_N], b[MAX_N];
int dp[2][MAX_N];
int way[2][MAX_N];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("lcs.inp", "r", stdin);
    freopen("lcs.out", "w", stdout);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> b[i];
    }

    bool now = 1, prev = 0;
    for (int i = 0; i <= m; i++) {
        way[prev][i] = 1;
    }
    way[now][0] = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i] == b[j]) {
                dp[now][j] = dp[prev][j - 1] + 1;
                way[now][j] = way[prev][j - 1];
            }
            else {
                if (dp[now][j - 1] == dp[prev][j]) {
                    dp[now][j] = dp[now][j - 1];
                    way[now][j] = 0;
                    add(way[now][j], way[now][j - 1]);
                    add(way[now][j], way[prev][j]);
                    if (dp[prev][j - 1] == dp[now][j]) {
                        add(way[now][j], mod - way[prev][j - 1]);
                    }
                }
                else {
                    if (dp[now][j - 1] > dp[prev][j]) {
                        dp[now][j] = dp[now][j - 1];
                        way[now][j] = way[now][j - 1];
                    }
                    else {
                        dp[now][j] = dp[prev][j];
                        way[now][j] = way[prev][j];
                    }
                }
            }
        }

        swap(now, prev);
    }

    cout << dp[prev][m] << " " << way[prev][m] << "\n";

    return 0;
}