Overview

This problem asks us to find the sum of “multiplicative inverses of products of prices” when selecting \(K\) items from \(N\) items. Although it may seem complex at first glance, by utilizing the property that “the inverse of a product equals the product of the inverses,” we can solve it efficiently using dynamic programming (DP).

Analysis

1. Utilizing the Properties of Multiplicative Inverses

Let the prices of the \(K\) selected items be \(A_{i_1}, A_{i_2}, \dots, A_{i_K}\), and their product be \(P = A_{i_1} A_{i_2} \cdots A_{i_K}\).

When \(P\) is not a multiple of \(M\), the points to be awarded are the multiplicative inverse of \(P\) modulo \(M\), i.e., \(P^{-1} \pmod M\). From the properties of multiplicative inverses, the following holds: $\(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\)$

In other words, “the inverse of the product of prices” equals “the product of the inverses of each price.”

2. Handling Items That Are Multiples of \(M\)

When a price \(A_i\) is a multiple of \(M\), its inverse does not exist. Furthermore, if even one such item is selected, the overall product \(P\) also becomes a multiple of \(M\), and the awarded points become \(0\).

Therefore, items whose prices are multiples of \(M\) can be excluded from the start. We keep only items where \(A_i \pmod M \neq 0\), and precompute each of their inverses \(B_i = A_i^{-1} \pmod M\).

3. Reformulating the Problem

Let \(B\) be the set of inverses of the remaining items after exclusion. If the number of elements in \(B\) (number of items) is less than \(K\), then no matter how we choose, a multiple of \(M\) must be included, so the total sum of points is \(0\).

If the number of elements is \(K\) or more, the desired value becomes “the sum of products obtained by choosing \(K\) elements from set \(B\) and multiplying them together.” This is equivalent to finding the coefficient of \(x^K\) in the following polynomial: $\(f(x) = \prod_{b \in B} (1 + b x)\)$

This coefficient can be computed efficiently using dynamic programming (DP).

Algorithm

1. Precomputation of Inverses For each item \(A_i\), determine whether \(A_i \pmod M \neq 0\). If the condition is satisfied, compute the inverse \(b = A_i^{M-2} \pmod M\) using Fermat’s little theorem (\(A_i^{-1} \equiv A_i^{M-2} \pmod M\)), and add it to the array \(B\).

2. Handling Corner Cases If the number of elements in array \(B\) is less than \(K\), output 0 and terminate.

3. Aggregation Using Dynamic Programming (DP) Compute the sum of products when choosing \(K\) elements from \(B\).

   • dp[j]: the sum of products when \(j\) elements have been chosen from the elements seen so far
   • Initial state: dp[0] = 1, all others are 0

For each element \(b \in B\), update the DP table from back to front (from \(j = K\) down to \(1\)) as follows: $\(\text{dp}[j] = (\text{dp}[j] + \text{dp}[j-1] \times b) \pmod M\)$

After performing the update for all \(b \in B\), dp[K] is the desired answer.

Complexity

• Time Complexity: \(O(N \log M + NK)\)

  • Computing the inverse of each item takes \(O(\log M)\) using fast exponentiation. Since there are at most \(N\) items, precomputation takes \(O(N \log M)\).
  • For the DP transitions, the inner loop runs \(K\) times for each of the \(N\) items, giving \(O(NK)\).
  • Overall, the complexity is \(O(N \log M + NK)\), which runs sufficiently fast for the constraints \(N, K \leq 5000\).

• Space Complexity: \(O(N + K)\)

  • The array \(B\) storing inverses uses \(O(N)\) memory, and the DP table uses \(O(K)\) memory.

Implementation Notes

• DP Update Order: By updating the DP table in reverse order from j = K to 1, we can perform correct transitions using only a 1-dimensional array (without overwriting old values). This keeps the space complexity at \(O(K)\).

• Avoiding Division by Zero: By excluding elements where \(A_i \pmod M = 0\) in advance, we eliminate the need to handle cases where the inverse does not exist (or becomes \(0\)), making the implementation simpler.

  Source Code

#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;
}

---

This editorial was generated by gemini-3.5-flash-thinking.