Overview

This is a counting problem where we need to determine how many subsequences of a sequence \(A\) of length \(N\) match a sequence \(P\) of length \(K\). By using dynamic programming (DP), we can efficiently compute this even for large \(N\).

Analysis

This problem is a classic counting problem dealing with “subsequences.”

1. Naive Dynamic Programming

First, consider the following DP state: - \(dp[i][j] :=\) the number of ways to form the first \(j\) elements of sequence \(P\) using the first \(i\) elements of sequence \(A\)

When examining \(A_i\), there are two choices: 1. Don’t use \(A_i\): \(dp[i-1][j]\) ways 2. Use \(A_i\): Only possible when \(A_i = P_j\), giving \(dp[i-1][j-1]\) ways

Therefore, the transition is as follows: - When \(A_i = P_j\): \(dp[i][j] = dp[i-1][j] + dp[i-1][j-1]\) - When \(A_i \neq P_j\): \(dp[i][j] = dp[i-1][j]\)

2. Optimizing Memory and Computation

Since \(N \leq 10^5, K \leq 100\), directly maintaining an \(O(NK)\) DP table would consume a lot of memory. However, since computing the \(i\)-th row only requires the results from the \((i-1)\)-th row, we can reuse the array to reduce the space complexity to \(O(K)\).

Additionally, checking all elements of \(P\) for each \(A_i\) takes \(O(NK)\). Since \(K\) is small, this is fast enough, but for further efficiency, we can precompute “where in \(P\) does the value matching \(A_i\) appear” using a dictionary (hash map), allowing us to update only the matching positions in a targeted manner.

Algorithm

Dynamic Programming Procedure

1. Preprocessing: For each value contained in sequence \(P\), compile a list of which indices (\(0\) to \(K-1\)) in \(P\) that value appears at.
2. DP Table Initialization: Let dp[j] be “the number of ways to form the first \(j\) elements of \(P\).”
   • dp[0] = 1 (there is exactly 1 way to form the empty subsequence by selecting nothing)
   • All other entries are initialized to 0.
3. Scanning Sequence \(A\): Process each element \(A_i\) of \(A\) one by one, performing the following:
   • If \(A_i\) appears in \(P\), retrieve all its indices \(j\).
   • For each index \(j\), update as dp[j+1] = (dp[j+1] + dp[j]) % MOD.

Important Note on Index Update Order

To prevent using the same \(A_i\) more than once within a single subsequence, the indices \(j\) must be updated from largest to smallest (in descending order). For example, if \(P = [1, 1]\) and the current element is \(A_i = 1\), updating in ascending order would first update dp[1], and then immediately use that updated value to update dp[2], effectively advancing two steps with a single \(A_i\).

Complexity

• Time Complexity: \(O(N + K + \sum_{i=1}^N (\text{number of times value } A_i \text{ appears in } P))\)
  • In the worst case, this is \(O(NK)\). With \(N=10^5, K=100\), this amounts to approximately \(10^7\) operations, which comfortably fits within the time limit.
• Space Complexity: \(O(N + K)\)
  • This depends on storing the sequences, the DP table, and the dictionary for index management.

Implementation Tips

• Using a Dictionary: Create a dictionary like val_to_indices to instantly look up the indices in \(P\) for a given value.

• Descending Order Update: By updating the DP from the back of the indices, such as for i in reversed(indices):, we correctly ensure that “each element is used at most once.”

• Fast Input: Since \(N\) can be large, reading all input at once using sys.stdin.read().split() or similar methods improves speed.

  Source Code

import sys

def solve():
    # Use fast I/O to read all input data at once
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Read N and K
    N = int(input_data[0])
    K = int(input_data[1])
    
    # Map the sequences A and P to integers
    # A is the original sequence, P is the target subsequence
    A = [int(x) for x in input_data[2 : 2 + N]]
    P = [int(x) for x in input_data[2 + N : 2 + N + K]]
    
    MOD = 1000000007
    
    # Pre-process positions of values in P
    # val_to_indices[v] will store all indices i such that P[i] == v.
    # We store them in descending order to update the DP table correctly
    # without using the same element of A multiple times for one subsequence.
    val_to_indices = {}
    for i in range(K - 1, -1, -1):
        val = P[i]
        if val not in val_to_indices:
            val_to_indices[val] = []
        val_to_indices[val].append(i)
    
    # dp[j] stores the number of ways to form the prefix P[0...j-1]
    # dp[0] = 1 represents the empty subsequence.
    dp = [0] * (K + 1)
    dp[0] = 1
    
    # Optimization: Filter out elements of A that do not appear in P.
    # This reduces the number of lookups in the main loop.
    relevant_indices = [val_to_indices[a] for a in A if a in val_to_indices]
    
    # Main DP loop
    # For each relevant element in A, we update the counts for all matching positions in P.
    for indices in relevant_indices:
        for i in indices:
            # dp[i+1] is the number of ways to form P[:i+1]
            # It can be extended by taking P[:i] and appending the current element.
            dp_i = dp[i]
            
            # If dp_i is 0, there's no way to form the prefix P[:i] yet, so we skip.
            if dp_i:
                new_val = dp[i+1] + dp_i
                # Apply modulo using a faster conditional subtraction
                if new_val >= MOD:
                    new_val -= MOD
                dp[i+1] = new_val
                
    # The answer is the number of ways to form the full target sequence P.
    print(dp[K])

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-preview.