概要

この問題は、商品の価格の積の逆元を求める問題ですが、逆元の性質「積の逆元は、それぞれの逆元の積に等しい」を利用することで、問題をシンプルに言い換えることができます。 各商品の価格の逆元をあらかじめ計算しておき、それらから \(K\) 個選んだ積の総和を動的計画法（DP）を用いて効率的に求める問題に帰着させます。

考察

1. 素朴なアプローチとその限界

すべての商品の選び方は \(\binom{N}{K}\) 通りあります。 例えば \(N = 5000, K = 2500\) のとき、選び方の数は天文学的な数字になり、すべての組み合わせについて積 \(P\) とその逆元を愚直に計算すると、実行時間制限（TLE）になってしまいます。

2. 逆元の性質を利用した言い換え

モジュロ演算における逆元には、以下の便利な性質があります。 積 \(P = A_{i_1} A_{i_2} \cdots A_{i_K}\) が \(M\) の倍数でないとき、法 \(M\) における \(P\) の逆元は以下のように分解できます。

\[ P^{-1} \equiv (A_{i_1} A_{i_2} \cdots A_{i_K})^{-1} \equiv A_{i_1}^{-1} A_{i_2}^{-1} \cdots A_{i_K}^{-1} \pmod M \]

つまり、「選んだ商品の価格の積の逆元」は、「選んだ商品の価格の逆元の積」と等しくなります。 これにより、あらかじめ各商品の価格の逆元を計算しておけば、問題は「逆元の集合から \(K\) 個を選んだときの積の総和を求める」という問題（基本対称式の計算）に単純化されます。

3. 価格が \(M\) の倍数である商品の扱い

価格 \(A_i\) が \(M\) の倍数である場合、その商品の逆元は存在しません。また、この商品を1つでも選ぶと、全体の積 \(P\) は \(M\) の倍数になり、獲得ポイントは \(0\) になります。 したがって、\(A_i \equiv 0 \pmod M\) となる商品は、最初からすべて除外して考えてよいです。

除外した結果、残った（逆元が存在する）商品の個数が \(K\) 個未満になった場合は、どのように選んでも必ず \(M\) の倍数が含まれてしまうため、ポイントの総和は \(0\) となります。

アルゴリズム

以下の手順で解を求めます。

1. 前処理（逆元の計算） 各商品 \(i\) について、\(A_i \pmod M \neq 0\) である場合のみ、フェルマーの小定理を用いて逆元 \(B_j \equiv A_i^{M-2} \pmod M\) を計算し、配列 \(B\) に追加します。

2. 要素数の判定 配列 \(B\) の要素数が \(K\) 未満であれば、答えは \(0\) です。

3. 動的計画法（DP）による積の総和の計算 配列 \(B\) の要素から \(K\) 個選んだ積の総和をDPで求めます。

   • dp[j] : これまでに見た要素から \(j\) 個選んだときの積の総和
   • 初期値: dp[0] = 1、それ以外は 0
   • 遷移: 配列 \(B\) の各要素 \(b\) について、 dp[j] = (dp[j] + dp[j-1] * b) % M （※同じ要素を重複して選ばないよう、j は \(K\) から \(1\) まで逆順に更新します）

4. 出力 最終的な答えは dp[K] となります。

計算量

• 時間計算量: \(O(N \log M + NK)\)

  • 各要素の逆元の計算には、繰り返し二乗法（pow 関数）を用いるため \(O(\log M)\) かかります。これを最大 \(N\) 回行うため \(O(N \log M)\) です。
  • DPの遷移は、要素数（最大 \(N\)） \(\times\) 選ぶ個数 \(K\) の二重ループとなるため \(O(NK)\) です。
  • \(N, K \le 5000\) より、全体の計算回数は約 \(2.5 \times 10^7\) 回となり、実行時間制限に十分間に合います。

• 空間計算量: \(O(N + K)\)

  • 逆元を格納する配列 \(B\) のサイズが最大 \(O(N)\)、DPテーブルのサイズが \(O(K)\) となり、非常に省メモリです。

実装のポイント

• 高速な逆元計算: Pythonでは pow(base, exp, mod) を使うことで、内部で繰り返し二乗法が適用され、高速に \(base^{exp} \pmod{mod}\) を計算できます。

• 1次元配列によるDPの最適化: DPの遷移の際、ループを逆順（limit から 1 へデクリメント）に回すことで、古い情報を上書きすることなく1次元配列のみで遷移を完結させています。これにより空間計算量を \(O(NK)\) から \(O(K)\) に削減しています。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    K = int(input_data[1])
    M = int(input_data[2])
    A = [int(x) for x in input_data[3:]]
    
    B = []
    for a in A:
        val = a % M
        if val != 0:
            B.append(pow(val, M - 2, M))
            
    if len(B) < K:
        print(0)
        return
        
    dp = [0] * (K + 1)
    dp[0] = 1
    
    count = 0
    for b in B:
        count += 1
        limit = min(K, count)
        for j in range(limit, 0, -1):
            dp[j] = (dp[j] + dp[j-1] * b) % M
            
    print(dp[K])

if __name__ == '__main__':
    solve()

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