Submission #6188060

---

Source Code Expand

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
using namespace std;
template <typename X, typename T> auto make_vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto make_vectors(X x, Y y, Z z, Zs... zs) { auto cont = make_vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

template <int32_t MOD>
struct mint {
    int32_t value;
    mint() : value() {}
    mint(int64_t value_) : value(value_ < 0 ? value_ % MOD + MOD : value_ >= MOD ? value_ % MOD : value_) {}
    inline mint<MOD> operator + (mint<MOD> other) const { int32_t c = this->value + other.value; return mint<MOD>(c >= MOD ? c - MOD : c); }
    inline mint<MOD> operator - (mint<MOD> other) const { int32_t c = this->value - other.value; return mint<MOD>(c <    0 ? c + MOD : c); }
    inline mint<MOD> operator * (mint<MOD> other) const { int32_t c = (int64_t)this->value * other.value % MOD; return mint<MOD>(c < 0 ? c + MOD : c); }
    inline mint<MOD> & operator += (mint<MOD> other) { this->value += other.value; if (this->value >= MOD) this->value -= MOD; return *this; }
    inline mint<MOD> & operator -= (mint<MOD> other) { this->value -= other.value; if (this->value <    0) this->value += MOD; return *this; }
    inline mint<MOD> & operator *= (mint<MOD> other) { this->value = (int64_t)this->value * other.value % MOD; if (this->value < 0) this->value += MOD; return *this; }
};
template <int32_t MOD> mint<MOD> operator * (int64_t value, mint<MOD> n) { return mint<MOD>(value) * n; }
template <int32_t MOD> std::ostream & operator << (std::ostream & out, mint<MOD> n) { return out << n.value; }


constexpr int MOD = 1e9 + 7;
mint<MOD> solve(int n, int m, const vector<int> & a, const vector<int> & b) {
    auto dp = make_vectors(n + 1, m + 1, mint<MOD>());
    auto sum = make_vectors(n + 1, m + 1, mint<MOD>());
    dp[0][0] = 1;
    REP (i, n + 1) {
        REP (j, m + 1) {
            if (i - 1 >= 0) sum[i][j] += sum[i - 1][j];
            if (j - 1 >= 0) sum[i][j] += sum[i][j - 1];
            if (i - 1 >= 0 and j - 1 >= 0) sum[i][j] -= sum[i - 1][j - 1];
            if (i - 1 >= 0 and j - 1 >= 0) sum[i][j] += dp[i - 1][j - 1];
            if (i - 1 >= 0 and j - 1 >= 0 and a[i - 1] == b[j - 1]) {
                dp[i][j] = sum[i][j];
            }
        }
    }
    mint<MOD> ans = 0;
    REP (i, n + 1) {
        REP (j, m + 1) {
            ans += dp[i][j];
        }
    }
    return ans;
}

int main() {
    int n, m; cin >> n >> m;
    vector<int> a(n);
    REP (i, n) {
        cin >> a[i];
    }
    vector<int> b(m);
    REP (j, m) {
        cin >> b[j];
    }
    cout << solve(n, m, a, b) << endl;
    return 0;
}

Submission Info

Judge Result