第3题

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

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

判断题

solve(n, n, a, a) 返回 $2^n$（　）。

{{ select(1) }}

• 正确
• 错误