概要

数列 \(A\) から要素をいくつか（順序を保って）選び、ちょうど数列 \(P\) と一致する部分列を作る方法の数を、\(10^9+7\) で割った余りで求めます。

考察

部分列の一致は「左から順に見て、\(P\) の次に欲しい値を見つけたら採用する／しない」という選択の積み重ねで数え上げられます。
この種の問題は典型的に DP（動的計画法）で解けます。

素朴な方法がダメな理由

• \(A\) から要素を選ぶ／選ばないの全探索は \(2^N\) 通りで、\(N \le 10^5\) では不可能です。
• 「\(A\) の各位置を使うかどうか」を状態にすると状態数が大きすぎます。

重要な観察

「\(P\) の先頭から何文字（何要素）まで作れたか」だけを覚えれば十分です。
つまり、今までに作れた \(P\) の接頭辞の長さ（0〜\(K\)）だけを状態にする DP にできます。

さらに、\(A_i\) を見たときに更新が必要なのは「\(P\) の中で値が \(A_i\) と一致する位置」だけです。
そこで、あらかじめ「値 \(v\) は \(P\) のどの位置に出るか」を辞書で持っておくと高速化できます。

アルゴリズム

DP 配列を次のように定義します。

• \(dp[t]\) := これまでに見た \(A\) の要素から、\(P\) の先頭 \(t\) 要素（\(P_0,\dots,P_{t-1}\)）と一致する部分列を作る方法の数
  （\(t=0\) は「空の部分列」なので常に 1 通りからスタート）

初期化： - \(dp[0]=1\), その他は 0

更新（\(A\) を左から順に見る）： - 現在の値を \(a\) とする - \(P\) の中で \(P_j = a\) となる位置 \(j\) について、
「長さ \(j\) まで作れているなら、この \(a\) を使って長さ \(j+1\) に伸ばせる」ので $\( dp[j+1] \leftarrow dp[j+1] + dp[j] \)$ を行います（mod を取る）。

ただしここで \(j\) を大きい方から逆順に更新するのが重要です。
順方向に更新すると、同じ \(A_i\) を 1 回見ただけなのに、その \(A_i\) を複数回使ったかのような更新が混ざってしまいます（同一要素の二重使用）。

具体例（イメージ）

\(P=[2,1]\)、今 \(dp=[1, x, y]\)（長さ0,1,2の作り方）だとして、\(a=2\) を見たら
\(P_0=2\) なので \(dp[1]+=dp[0]\) が起き、「2 まで作れる方法」が増えます。
次に \(a=1\) を見たら \(P_1=1\) なので \(dp[2]+=dp[1]\) が起き、「2,1 まで作れる方法」が増えます。
これを全ての \(A_i\) で繰り返すと、最終的な答えは \(dp[K]\) になります。

計算量

• 時間計算量: \(O\!\left(\sum_{i=1}^{N} (\text{\)A_i\( が \)P\( に現れる回数})\right)\)（最悪でも \(O(NK)\)）
• 空間計算量: \(O(K)\)（DP 配列）＋ \(O(K)\)（値→位置リストの辞書）

実装のポイント

• 値→位置（添字）リストを作る：pos[v] = [j1, j2, ...]（\(P_{j}=v\) の全ての \(j\)）

• 更新は必ず 逆順：for j in reversed(lst): dp[j+1] += dp[j]

• mod \(10^9+7\) を毎回取ってオーバーフロー・巨大化を防ぐ

• \(K \le 100\) なので DP 配列は小さく、\(N \le 10^5\) でも十分高速に動きます

  ソースコード

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()

---

この解説は gpt-5.2-high によって生成されました。