Overview

This is a problem of counting the number of ways to select a subsequence from sequence \(A\) such that it matches sequence \(P\).

Analysis

This problem is a classic “subsequence matching” counting problem. A naive brute-force approach (e.g., deciding for each element of \(A\) whether to include it or not) would take exponential time and is impractical.

The key observation is that in the process of “building a subsequence while preserving order,” we only need to track how far we have matched so far. In other words, dynamic programming (DP) is effective here.

We define the DP table as follows: - \(dp[i][j]\) := the number of ways to form a subsequence using the first \(i\) elements of \(A\) that matches the first \(j\) elements of \(P\)

The transitions are as follows: - In any case, we can skip \(A[i-1]\), so \(dp[i][j] += dp[i-1][j]\) - If \(A[i-1] = P[j-1]\), we can use \(A[i-1]\) to match \(P[j-1]\), so \(dp[i][j] += dp[i-1][j-1]\)

The initial conditions are: - \(dp[0][0] = 1\) (there is exactly one way to match the empty subsequence with the empty sequence) - \(dp[0][j] = 0\) (it is impossible to match anything with no elements)

However, implementing this two-dimensional DP directly results in \(O(NK)\) space complexity, which may not fit in memory when the constraint is \(N = 10^5\).

To improve space efficiency, we use the technique of updating \(j\) in reverse order. This allows us to simulate the DP using a one-dimensional array.

Specifically, we maintain \(dp[j]\) as “the number of ways to match the first \(j\) elements of \(P\) using elements of \(A\) up to the current one,” and process \(j\) in descending order during updates. This prevents the same element from being used multiple times.

Algorithm

We use dynamic programming (DP).

• \(dp[j]\) := the number of subsequences matching the first \(j\) elements of \(P\), using elements of \(A\) up to the current one
• Initial value: \(dp[0] = 1\) (there is exactly one empty subsequence)
• For each \(A[i]\):
  • Iterate \(j\) from \(K\) down to \(1\) in reverse order
  • If \(A[i] = P[j-1]\), then \(dp[j] = (dp[j] + dp[j-1]) \bmod MOD\)
• The final answer is \(dp[K]\)

In this way, the space complexity is reduced to \(O(K)\).

Complexity

• Time complexity: \(O(NK)\)
• Space complexity: \(O(K)\)

Implementation Notes

• By iterating \(j\) in descending order during the DP update, we prevent using the same \(A[i]\) multiple times
• \(dp[0]\) always remains 1 (there is always exactly one way to match the empty sequence)
• Don’t forget to take the modulo (MOD)

## Source Code

```python
MOD = 10**9 + 7

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:2+N]))
    P = list(map(int, data[2+N:2+N+K]))
    
    # dp[i][j] := Aの最初のi要素を使ってPの最初のj要素と一致する部分列の数
    # 添字を1-originで考えると分かりやすいが、0-originで実装する
    # dp[i][j] = (Aのi番目までを使って、Pのj番目までを一致させる方法の数)
    
    # dp[i][j] を更新するときに:
    # A[i-1] == P[j-1] なら、dp[i-1][j-1] の分を加算できる
    # どの場合でも、A[i-1]を使わずにすすめる dp[i-1][j] も加算
    
    # 初期化
    # dp[0][0] = 1 (空の部分列で空列に一致)
    # dp[0][j] = 0 (Aの空集合で非空なPは作れない)
    
    # 実際には二次元DPを左右から更新していく形になるが、
    # 空間効率を良くするために、Pの長さK+1の一次元配列で処理する
    
    dp = [0] * (K + 1)
    dp[0] = 1  # 空の部分列で一致する方法は1通り
    
    for i in range(N):
        # 後ろから更新することで、同じ要素を複数回使ってしまうのを防ぐ
        for j in range(K, 0, -1):
            if A[i] == P[j-1]:
                dp[j] = (dp[j] + dp[j-1]) % MOD
        # dp[0] は常に1なので更新しない
        
    print(dp[K])

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.