この問題は DP で解くことができます。

\(\mathrm{DP}[i][j]\) を「 \((A_1,\dots,A_i)\) の部分列で \((P_1,\ldots, P_j)\) と一致するものの個数」とします。求める答えは \(\mathrm{DP}[N][K]\) です。

このとき、 \(\mathrm{DP}[i][j]\) は \(A_i=P_j\) のときに限り \(A_i\) を選ぶかどうか選択でき、次のように定まります。

\(\mathrm{DP}[i][j]=\begin{cases} \mathrm{DP}[i-1][j] + \mathrm{DP}[i-1][j-1] &A_i=P_j \text{ のとき}\\ \mathrm{DP}[i-1][j] & A_i\neq P_j \text{ のとき} \end{cases}\)

この DP で \(\mathrm{DP}[N][K]\) を求めるには状態数 \(O(NK)\) 、各状態の計算が \(O(1)\) であることから \(O(NK)\) で計算できます。

実装例 (C++)

#include<bits/stdc++.h>
#include<atcoder/modint>
using namespace std;
using mint = atcoder::modint1000000007;

int main(){
  int n, k;
  cin >> n >> k;
  vector<int>a(n);
  for(int i=0; i<n; i++) cin >> a[i];
  vector<int>p(k);
  for(int i=0; i<k; i++) cin >> p[i];

  vector<vector<mint>>dp(n+1, vector<mint>(k+1));
  for(int i=0; i<n+1; i++){
    dp[i][0] = 1;
  }

  for(int i=0; i<n; i++){
    for(int j=0; j<k; j++){
      if(a[i] == p[j]){
        dp[i+1][j+1] = dp[i][j+1] + dp[i][j];
      }else{
        dp[i+1][j+1] = dp[i][j+1];
      }
    }
  }
  cout << dp[n][k].val() << endl;
}

実装例 (Python)

MOD = 10**9+7
N, K = map(int, input().split())
A = list(map(int, input().split()))
P = list(map(int, input().split()))

dp = [[0]*(K+1) for _ in range(N+1)]
for i in range(N+1):
  dp[i][0] = 1

for i in range(N):
  for j in range(K):
    if A[i] == P[j]:
      dp[i+1][j+1] = (dp[i][j+1] + dp[i][j]) % MOD
    else:
      dp[i+1][j+1] = dp[i][j+1]

print(dp[N][K])