Advertisement
balsan

Untitled

Jun 19th, 2019
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.56 KB | None | 0 0
  1. #include<iostream>
  2. #define rep(i,n) for(int i=0;i<n;++i)
  3. using namespace std;
  4.  
  5. const int MOD = 1e9 + 7, LIM = 2001;
  6. int N, M, S[LIM], T[LIM], sum[LIM][LIM], dp[LIM][LIM], ans = 1;
  7.  
  8. int main() {
  9.     cin >> N >> M;
  10.     rep(i, N) cin >> S[i];
  11.     rep(i, M) cin >> T[i];
  12.  
  13.     rep(i, N) rep(j, M) {
  14.         if (S[i] == T[j]) {
  15.             dp[i+1][j+1] = (sum[i][j] + 1) % MOD;
  16.         }
  17.         sum[i+1][j+1] = (sum[i+1][j] + sum[i][j+1] - sum[i][j] + dp[i+1][j+1]) % MOD;
  18.         ans += dp[i+1][j+1];
  19.         ans %= MOD;
  20.     }
  21.     cout << ans << endl;
  22. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement