概要

長さ \(N\) の数列 \(A\) から、長さ \(K\) の数列 \(P\) と一致する部分列をいくつ作れるかを数え上げる問題です。 動的計画法（DP）を用いることで、大きな \(N\) に対して効率的に計算することができます。

考察

この問題は「部分列」を扱う典型的な数え上げ問題です。

1. 素朴な動的計画法

まず、以下のような DP 状態を考えます。 - \(dp[i][j] :=\) 数列 \(A\) の \(i\) 番目までの要素を使って、数列 \(P\) の \(j\) 番目までの部分列を作る方法の数

\(A_i\) を見る際、以下の 2 つの選択肢があります。 1. \(A_i\) を使わない場合: \(dp[i-1][j]\) 通り 2. \(A_i\) を使う場合: \(A_i = P_j\) であるときのみ可能で、\(dp[i-1][j-1]\) 通り

よって、遷移式は次のようになります。 - \(A_i = P_j\) のとき：\(dp[i][j] = dp[i-1][j] + dp[i-1][j-1]\) - \(A_i \neq P_j\) のとき：\(dp[i][j] = dp[i-1][j]\)

2. メモリと計算量の最適化

\(N \leq 10^5, K \leq 100\) であるため、上記のような \(O(NK)\) の DP テーブルをそのまま持つとメモリ消費が大きくなります。しかし、現在の \(i\) 番目の計算には \(i-1\) 番目の結果しか必要ないため、配列を使い回して \(O(K)\) の空間計算量に削減できます。

また、各 \(A_i\) に対して \(P\) の全要素をチェックすると \(O(NK)\) かかります。\(K\) が小さいためこれでも間に合いますが、より効率的にするために、「\(A_i\) と一致する値が \(P\) のどこにあるか」をあらかじめ辞書（ハッシュマップ）などで記録しておくと、一致する箇所だけをピンポイントで更新できます。

アルゴリズム

動的計画法の手順

1. 事前準備: 数列 \(P\) に含まれる各値について、その値が \(P\) 内のどのインデックス（\(0\) から \(K-1\)）にあるかをリストにまとめておきます。
2. DPテーブルの初期化: dp[j] を「\(P\) の先頭 \(j\) 個までを作る方法の数」とします。
   • dp[0] = 1（何も選ばない空の部分列は 1 通り）
   • それ以外は 0 で初期化します。
3. 数列 \(A\) の走査: \(A\) の要素 \(A_i\) を 1 つずつ取り出し、以下の処理を行います。
   • \(A_i\) が \(P\) に含まれている場合、そのインデックス \(j\) をすべて取得します。
   • 各インデックス \(j\) について、dp[j+1] = (dp[j+1] + dp[j]) % MOD と更新します。

インデックス更新の注意点

同じ \(A_i\) を 1 つの部分列の中で 2 回以上使ってしまうのを防ぐため、インデックス \(j\) の更新は大きい方から（降順に）行う必要があります。 例えば \(P = [1, 1]\)、現在の要素 \(A_i = 1\) のとき、昇順に更新すると dp[1] を更新した直後にその値を使って dp[2] を更新してしまい、1 つの \(A_i\) で 2 段階進んでしまうことになります。

計算量

• 時間計算量: \(O(N + K + \sum_{i=1}^N (\text{値 } A_i \text{ が } P \text{ に現れる回数}))\)
  • 最悪ケースでも \(O(NK)\) です。\(N=10^5, K=100\) なので、約 \(10^7\) 回の計算となり、制限時間内に十分収まります。
• 空間計算量: \(O(N + K)\)
  • 数列の保持と DP テーブル、インデックス管理用の辞書に依存します。

実装のポイント

• 辞書の活用: val_to_indices のような辞書を作り、値から \(P\) 内のインデックスを即座に引けるようにします。

• 降順更新: for i in reversed(indices): のように、インデックスの後ろから DP を更新することで、正しく「1 つの要素を 1 回だけ使う」計算ができます。

• 高速な入力: \(N\) が大きいため、sys.stdin.read().split() などを用いて一括で入力を読み込むと高速です。”`

  ソースコード

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

---

この解説は gemini-3-flash-preview によって生成されました。