Overview

This problem asks us to efficiently count the number of ways to select elements from sequence \(A\) while preserving order to form a subsequence that exactly matches pattern sequence \(P\), using dynamic programming (DP).

Analysis

Understanding the Problem

For example, consider \(A = [1, 2, 1, 2]\) and \(P = [1, 2]\). - \((A_1, A_2) = (1, 2)\) → match ✓ - \((A_1, A_4) = (1, 2)\) → match ✓ - \((A_3, A_4) = (1, 2)\) → match ✓

As shown, different positions count as different methods, so the answer is \(3\) ways.

Problems with the Naive Approach

If we enumerate all subsequences, the number of ways to choose a subsequence of length \(K\) from a sequence of length \(N\) is at most \(\binom{N}{K}\). When \(N = 10^5\) and \(K = 100\), this becomes an astronomical number, making TLE (Time Limit Exceeded) inevitable.

Solution: Dynamic Programming

We sequentially compute “how many subsequences match the first \(j\) elements of \(P\)”. We examine each element of \(A\) one by one and handle cases based on which position in \(P\) it matches.

Algorithm

DP Definition

\(dp[j]\) = the number of ways to form a subsequence matching the first \(j\) elements of \(P\) using elements of \(A\) seen so far

Initial State

• \(dp[0] = 1\) (there is exactly one empty subsequence)
• \(dp[1], dp[2], \ldots, dp[K] = 0\)

Transition

For each element \(A[i]\) in \(A\): - If \(A[i] = P[j]\), add \(dp[j]\) to \(dp[j+1]\) - This means transitioning from “the state where the first \(j\) elements of \(P\) are matched” to “the state where \(j+1\) elements are matched by selecting \(A[i]\)”

Importance of Update Order

We must update in reverse order (from \(j = K-1\) to \(j = 0\)).

If we update in forward order, we might use the same \(A[i]\) multiple times. For example, updating \(dp[0] \to dp[1] \to dp[2]\) would mean a single \(A[i]\) matched both \(P[0]\) and \(P[1]\).

In reverse order, when updating \(dp[j+1]\), \(dp[j]\) still holds the old value (the value before using \(A[i]\)), so the calculation is correct.

Example Walkthrough

For \(A = [1, 2, 1]\) and \(P = [1, 1]\):

Operation	\(dp[0]\)	\(dp[1]\)	\(dp[2]\)
Initial	1	0	0
Process \(A[0]=1\)	1	1	0
Process \(A[1]=2\)	1	1	0
Process \(A[2]=1\)	1	2	1

The answer is \(dp[2] = 1\) (only the combination of positions \(0\) and \(2\))

Complexity

• Time Complexity: \(O(N \times K)\)
  • For each element of \(A\) (\(N\) elements), check each position in \(P\) (\(K\) positions)
• Space Complexity: \(O(K)\)
  • Size of the DP array

Implementation Notes

1. Reverse Loop: Using for j in range(K - 1, -1, -1) processes \(j\) from large to small, preventing duplicate use of the same element
2. MOD Operation: Since the answer can become very large, take the remainder modulo \(10^9 + 7\) after each addition
3. 1D DP is Sufficient: Instead of using a 2D array \(dp[i][j]\) (matching \(j\) elements of \(P\) after seeing the first \(i\) elements of \(A\)), reverse-order updating allows us to achieve this with 1D

Source Code

def solve():
    MOD = 10**9 + 7
    
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    P = list(map(int, input().split()))
    
    # dp[j] = number of subsequences matching the first j elements of P
    # dp[0] = 1 (empty subsequence)
    dp = [0] * (K + 1)
    dp[0] = 1
    
    for i in range(N):
        # Update using A[i]
        # Must update in reverse order to avoid using the same A[i] multiple times
        for j in range(K - 1, -1, -1):
            if A[i] == P[j]:
                dp[j + 1] = (dp[j + 1] + dp[j]) % MOD
    
    print(dp[K])

solve()

---

This editorial was generated by claude4.5opus.