Overview

From the sequence \(A\), select some elements (preserving their order) to form a subsequence that exactly matches the sequence \(P\). Find the number of ways to do this, modulo \(10^9+7\).

Approach

Matching a subsequence can be counted by the accumulation of choices: “scanning from left to right, when we find the next value needed for \(P\), we either take it or skip it.” This type of problem is typically solvable with DP (dynamic programming).

Why a naive approach doesn’t work

• Trying all subsets of whether to select each element of \(A\) gives \(2^N\) possibilities, which is infeasible for \(N \le 10^5\).
• Using “whether each position of \(A\) is used or not” as the state results in too many states.

Key observation

It suffices to only keep track of “how many elements from the beginning of \(P\) have been matched so far.” In other words, we can design a DP where the only state is the length of the matched prefix of \(P\) (from \(0\) to \(K\)).

Furthermore, when we look at \(A_i\), we only need to update positions in \(P\) where the value equals \(A_i\). Therefore, we can speed things up by precomputing a dictionary mapping “value \(v\) to the positions in \(P\) where it appears.”

Algorithm

Define the DP array as follows:

• \(dp[t]\) := the number of ways to form a subsequence matching the first \(t\) elements of \(P\) (\(P_0, \dots, P_{t-1}\)) from the elements of \(A\) seen so far. (\(t=0\) corresponds to the “empty subsequence,” so it always starts at 1.)

Initialization: - \(dp[0]=1\), all others are 0.

Update (scan \(A\) from left to right): - Let the current value be \(a\). - For each position \(j\) in \(P\) where \(P_j = a\): “If we have already matched up to length \(j\), we can use this \(a\) to extend the match to length \(j+1\),” so we perform: $\( dp[j+1] \leftarrow dp[j+1] + dp[j] \)$ (taking mod as needed).

However, it is crucial to update \(j\) in reverse order (from largest to smallest). If we update in forward order, a single occurrence of \(A_i\) could be counted as if it were used multiple times (double-counting the same element).

Concrete example (illustration)

Suppose \(P=[2,1]\) and currently \(dp=[1, x, y]\) (number of ways for lengths 0, 1, 2). When we see \(a=2\): Since \(P_0=2\), we get \(dp[1] += dp[0]\), increasing the “number of ways to match up to 2.” Next, when we see \(a=1\): since \(P_1=1\), we get \(dp[2] += dp[1]\), increasing the “number of ways to match up to 2, 1.” Repeating this for all \(A_i\), the final answer is \(dp[K]\).

Complexity

• Time complexity: \(O\!\left(\sum_{i=1}^{N} (\text{number of times \)A_i\( appears in \)P\(})\right)\) (at worst \(O(NK)\))
• Space complexity: \(O(K)\) (DP array) + \(O(K)\) (dictionary mapping values to position lists)

Implementation details

• Build a value-to-position (index) list: pos[v] = [j1, j2, ...] (all \(j\) where \(P_{j}=v\))

• Always update in reverse order: for j in reversed(lst): dp[j+1] += dp[j]

• Take mod \(10^9+7\) at every step to prevent overflow and excessively large numbers

• Since \(K \le 100\), the DP array is small, and this runs efficiently even for \(N \le 10^5\)

  Source Code

import sys

MOD = 10**9 + 7

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, K = data[0], data[1]
    A = data[2:2+N]
    P = data[2+N:2+N+K]

    pos = {}
    for j, v in enumerate(P):
        pos.setdefault(v, []).append(j)

    dp = [0] * (K + 1)
    dp[0] = 1

    for a in A:
        lst = pos.get(a)
        if not lst:
            continue
        for j in reversed(lst):
            dp[j + 1] = (dp[j + 1] + dp[j]) % MOD

    print(dp[K] % MOD)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.