概要

数列 \(A\) から部分列を選んで、それが数列 \(P\) と一致するような選び方が何通りあるかを数える問題です。

考察

この問題は典型的な「部分列マッチング」の数え上げ問題です。素朴な全探索（例えば、\(A\) の各要素について使う・使わないを決める）では、指数時間になってしまい現実的ではありません。

重要な観察としては、「順序を保ちながら部分列を作っていく」過程において、途中までの一致状況だけを管理すれば良いという点です。つまり、動的計画法（DP）が有効です。

DPテーブルとして以下のように定義します： - \(dp[i][j]\) := \(A\) の最初の \(i\) 要素を使って、\(P\) の最初の \(j\) 要素と一致する部分列の作り方の数

遷移は以下のようになります： - どの場合でも、\(A[i-1]\) を使わずに進めるので、\(dp[i][j] += dp[i-1][j]\) - もし \(A[i-1] = P[j-1]\) ならば、\(A[i-1]\) を使って \(P[j-1]\) にマッチさせられるので、\(dp[i][j] += dp[i-1][j-1]\)

初期条件は： - \(dp[0][0] = 1\) （空の部分列は空列に一致する方法が1通り） - \(dp[0][j] = 0\) （要素がないのに一致させるのは無理）

しかし、この二次元DPをそのまま実装すると空間計算量が \(O(NK)\) となり、制約 \(N = 10^5\) のときメモリに乗らない可能性があります。

そこで、空間効率を改善するために、\(j\) を後ろから更新するテクニックを使います。これにより、一次元配列でDPをシミュレートできます。

具体的には、\(dp[j]\) が「今見ている \(A\) の要素までを使って、\(P\) の最初の \(j\) 文字と一致する方法の数」として管理し、更新時には \(j\) を降順に処理します。これによって、同じ要素を複数回使ってしまうことを防ぎます。

アルゴリズム

動的計画法（DP）を使います。

• \(dp[j]\) := 現在の \(A\) の要素までを使って、\(P\) の最初の \(j\) 要素と一致する部分列の数
• 初期値：\(dp[0] = 1\)（空の部分列は1通り）
• 各 \(A[i]\) に対して：
  • \(j = K\) から \(1\) まで逆順に走査
  • もし \(A[i] = P[j-1]\) なら、\(dp[j] = (dp[j] + dp[j-1]) \bmod MOD\)
• 最終的に \(dp[K]\) が答え

このようにして、空間計算量を \(O(K)\) に抑えることができます。

計算量

• 時間計算量: \(O(NK)\)
• 空間計算量: \(O(K)\)

実装のポイント

• DPの更新時に \(j\) を降順に回すことで、同じ \(A[i]\) を複数回使ってしまうのを防ぐ
• \(dp[0]\) は常に1のままにしておく（空列に一致する方法は常に1通り）
• MODを忘れずに取る

## ソースコード

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

---

この解説は qwen3-coder-480b によって生成されました。