第2题

int a[maxn];
int b[maxn];
int n, m;

const long long mod = 1'000'000'007;
bool filled[maxn][maxn];
long long mem[maxn][maxn];

long long solve(int i, int j)
{
    if (i == n) return 1;
    if (j == m) return 1;
    if (filled[i][j])
        return mem[i][j];
    filled[i][j] = true;

    long long sum = solve(i+1, j) + solve(i, j+1);
    if (a[i] == b[j]) {
        return mem[i][j] = sum % mod;
    }
    else {
        return mem[i][j] = (sum - solve(i+1, j+1)) % mod;
    }
}

int main()
{
    std::cin >> n >> m;
    for (int i = 0; i < n; ++i) std::cin >> a[i];
    for (int i = 0; i < m; ++i) std::cin >> b[i];
    std::cout << (solve(0, 0) + mod) % mod << "\n";
}

该程序的时间复杂度为（ ）。

{{ select(1) }}

• $\Theta(n+m)$
• $\Theta(n \cdot m)$
• $\Theta(2^{m+n})$
• $\Theta(n \log m)$