概要

この問題は、\(N\) 個の商品から \(K\) 個を選んだときの「価格の積の乗法逆元」の総和を求める問題です。一見すると複雑そうですが、「積の逆元は、逆元の積に等しい」という性質を利用することで、動的計画法（DP）を用いて効率的に解くことができます。

考察

1. 乗法逆元の性質を利用する

選んだ \(K\) 個の商品の価格を \(A_{i_1}, A_{i_2}, \dots, A_{i_K}\) とし、その積を \(P = A_{i_1} A_{i_2} \cdots A_{i_K}\) とします。

\(P\) が \(M\) の倍数でないとき、求めるポイントは \(P\) の法 \(M\) における乗法逆元 \(P^{-1} \pmod M\) です。乗法逆元の性質から、以下が成り立ちます。 $\(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\)$

つまり、「価格の積の逆元」は「各価格の逆元の積」に等しくなります。

2. \(M\) の倍数である商品の扱い

価格 \(A_i\) が \(M\) の倍数である場合、その商品の逆元は存在しません。また、そのような商品を \(1\) つでも選ぶと、全体の積 \(P\) も \(M\) の倍数になり、付与されるポイントは \(0\) になります。

したがって、価格が \(M\) の倍数である商品は最初から除外して考えてよいです。 \(A_i \pmod M \neq 0\) であるような商品のみを残し、それぞれの逆元 \(B_i = A_i^{-1} \pmod M\) をあらかじめ計算しておきます。

3. 問題の言い換え

除外した後に残った商品の逆元の集合を \(B\) とします。 もし \(B\) の要素数（商品の個数）が \(K\) 未満であれば、どのように選んでも必ず \(M\) の倍数の商品が含まれてしまうため、ポイントの総和は \(0\) になります。

要素数が \(K\) 以上の場合、求める値は 「集合 \(B\) から \(K\) 個の要素を選んで掛け合わせたものの総和」 になります。 これは、以下の多項式の \(x^K\) の係数を求める問題と同値です。 $\(f(x) = \prod_{b \in B} (1 + b x)\)$

この係数は、動的計画法（DP）を用いて高速に計算することができます。

アルゴリズム

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

2. コーナーケースの処理 配列 \(B\) の要素数が \(K\) 未満である場合は、0 を出力して終了します。

3. 動的計画法（DP）による集計 \(B\) の要素から \(K\) 個選ぶ組み合わせの積の和を求めます。

   • dp[j]：これまでに見た要素から \(j\) 個選んだときの積の和
   • 初期状態：dp[0] = 1、それ以外は 0

各要素 \(b \in B\) について、DPテーブルを後ろから（\(j = K\) から \(1\) に向かって）以下のように更新します。 $\(\text{dp}[j] = (\text{dp}[j] + \text{dp}[j-1] \times b) \pmod M\)$

すべての \(b \in B\) について更新を行った後、dp[K] が求める答えになります。

計算量

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

  • 各商品の逆元を求めるのに、繰り返し二乗法を用いて \(O(\log M)\) かかります。商品数は最大 \(N\) 個なので、事前計算に \(O(N \log M)\) かかります。
  • DPの遷移は、商品数 \(N\) に対し、内側のループが \(K\) 回回るため \(O(NK)\) です。
  • 全体として \(O(N \log M + NK)\) となり、制約の \(N, K \leq 5000\) に対し十分高速に動作します。

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

  • 逆元を格納する配列 \(B\) に \(O(N)\)、DPテーブルに \(O(K)\) のメモリを使用します。

実装のポイント

• DPの更新順序: DPテーブルを j = K から 1 へと逆順に更新することで、1次元配列のみで（古い値を上書きすることなく）正しく遷移させることができます。これにより、空間計算量を \(O(K)\) に抑えています。

• ゼロ除算の回避: \(A_i \pmod M = 0\) の要素をあらかじめ除外することで、逆元が存在しない（または \(0\) になる）ケースを考慮する必要がなくなり、実装がシンプルになります。

  ソースコード

#include <iostream>
#include <vector>

using namespace std;

long long power(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return res;
}

long long modInverse(long long n, long long mod) {
    return power(n, mod - 2, mod);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, K;
    long long M;
    if (!(cin >> N >> K >> M)) return 0;

    vector<long long> B;
    B.reserve(N);
    for (int i = 0; i < N; ++i) {
        long long a;
        cin >> a;
        if (a % M != 0) {
            B.push_back(modInverse(a % M, M));
        }
    }

    if ((int)B.size() < K) {
        cout << 0 << "\n";
        return 0;
    }

    vector<long long> dp(K + 1, 0);
    dp[0] = 1;

    for (long long b : B) {
        for (int j = K; j >= 1; --j) {
            dp[j] = (dp[j] + dp[j-1] * b) % M;
        }
    }

    cout << dp[K] << "\n";

    return 0;
}

---

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