Overview

This problem asks us to select some items (club activities) from \(N\) items and count the number of combinations whose total value is a multiple of \(K\). A key characteristic of the constraints is that while \(N\) can be as large as \(10^5\), \(K\) is very small at most \(100\).

Analysis

1. Basic Dynamic Programming (DP)

The first approach that comes to mind is a DP defined as “\(dp[i][j] =\) the number of combinations considering club activities up to the \(i\)-th one, where the sum of activity points modulo \(K\) equals \(j\).” However, this has a time complexity of \(O(N \times K)\), which results in about \(10^7\) operations under the given constraints (\(N=10^5, K=100\)). In Python, simple loops may not finish within the time limit, so we consider a more efficient approach.

2. Generating Functions and Polynomials

The choice of selecting or not selecting each club activity can be represented by the polynomial \((1 + x^{A_i})\). The combination of all club activities can be expressed as the product of the following polynomials: $\(P(x) = \prod_{i=1}^N (1 + x^{A_i})\)\( When this polynomial is expanded, the coefficient of \)x^m\( represents "the number of combinations whose total points equal \)m\(." Since we want to find the count where "the total is a multiple of \)K\(," it suffices to manage polynomial degrees by their remainder when divided by \)K\(. In other words, **we compute the product of polynomials under the relation \)x^K - 1 \equiv 0\( (i.e., \)x^K \equiv 1$)**. This is the same operation known as “cyclic convolution.”

3. Speeding Up the Computation

By grouping club activities with the same remainder, we can significantly reduce the computation. - If there are \(c\) club activities whose activity points have remainder \(r\) when divided by \(K\), their contribution to the product is \((1 + x^r)^c\). - To compute \((1 + x^r)^c \pmod{x^K - 1}\), we first compute \((1 + x)^c \pmod{x^K - 1}\) using exponentiation by squaring, and then substitute \(x^r\) for \(x\) to obtain the result efficiently.

Algorithm

1. Count by remainder: Count the remainder \(r\) of each \(A_i\) divided by \(K\) (counts[r]).
2. Special case (\(r=0\)): If there are \(c_0\) club activities with remainder \(0\), selecting any subset of them does not affect the total’s remainder. Since each activity has 2 choices (join or not), we multiply the overall result by \(2^{c_0}\).
3. Polynomial exponentiation by repeated squaring:
   • For each \(r \in \{1, \dots, K-1\}\), compute \((1 + x)^c \pmod{x^K - 1}\) for each distinct count \(c = counts[r]\) using binary exponentiation.
   • Using binary exponentiation, the polynomial multiplication can be computed in \(O(K^2 \log N)\).
4. Polynomial composition:
   • From the computed \((1 + x)^c\), construct \((1 + x^r)^c\) for each \(r\).
   • Multiply all of these together to obtain the final polynomial \(dp\).
5. Output the answer:
   • \(dp[0]\) is the number of combinations where “the total is a multiple of \(K\) (remainder 0).”
   • This includes the 1 case of “selecting nothing (empty set),” so we subtract \(1\) and output the result modulo \(10^9+7\).

Complexity

• Time complexity: \(O(N + K^3 \log N)\)
  • The initial counting takes \(O(N)\).
  • Polynomial exponentiation (binary exponentiation) takes \(O(K^2 \log N)\). Doing this for up to \(K\) distinct remainders gives \(O(K^3 \log N)\).
  • Polynomial multiplication (cyclic convolution) takes \(O(K^3)\).
  • Since \(K=100\), we have \(K^3 = 10^6\), which is sufficiently fast.
• Space complexity: \(O(K^2)\)
  • Memory needed for caching exponentiation results and storing the DP table.

Implementation Notes

• Optimizing polynomial multiplication: In Python, taking % MOD inside inner loops is slow, so we accumulate the sum first and take the remainder at the end.

• Handling \(K=1\): When \(K=1\), all combinations satisfy the condition. We directly compute and output \(2^N - 1\).

• Handling negative remainders: Since dp[0] - 1 may become negative, we use (dp[0] - 1) % MOD to correctly compute the remainder.

  Source Code

import sys

# The problem asks for the number of non-empty subsets of clubs such that the sum of their activity points is a multiple of K.
# We use dynamic programming with generating functions.
# For each remainder r (mod K), let c be the number of clubs with activity point A_i % K = r.
# The generating function for these clubs is (1 + x^r)^c mod (x^K - 1).
# We can compute this as W_c(x^r) mod (x^K - 1), where W_c(x) = (1 + x)^c mod (x^K - 1).
# Since K is small (K <= 100), we can perform polynomial multiplication and exponentiation efficiently.

def solve():
    # Fast I/O: Read all input at once
    data = sys.stdin.read().split()
    if not data:
        return
    N = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:]))
    
    MOD = 10**9 + 7

    if K == 1:
        # If K=1, any non-empty subset of N clubs works.
        # Total number of non-empty subsets is 2^N - 1.
        print((pow(2, N, MOD) - 1) % MOD)
        return

    # Count frequencies of each remainder modulo K.
    counts = [0] * K
    for a in A:
        counts[a % K] += 1

    # Polynomial multiplication modulo (x^K - 1).
    # This is equivalent to a cyclic convolution of length K.
    def poly_mul(P, Q, K, MOD):
        res = [0] * K
        for i in range(K):
            pi = P[i]
            if pi == 0:
                continue
            # Summing products without modulo to speed up the inner loop.
            # Max value of res[k] is approx K * MOD^2, which is ~10^20.
            # Python handles arbitrary precision integers automatically.
            for j in range(K - i):
                res[i + j] += pi * Q[j]
            for j in range(i):
                res[j] += pi * Q[K - i + j]
        # Apply modulo once for each coefficient at the end of the multiplication.
        return [v % MOD for v in res]

    # Polynomial exponentiation modulo (x^K - 1).
    def poly_pow(P, n, K, MOD):
        res = [0] * K
        res[0] = 1
        base = P
        while n > 0:
            if n % 2 == 1:
                res = poly_mul(res, base, K, MOD)
            base = poly_mul(base, base, K, MOD)
            n //= 2
        return res

    # dp[j] is the number of ways to choose a subset with sum congruent to j mod K.
    # Initially, only the empty set exists with sum 0.
    dp = [0] * K
    dp[0] = 1

    # Precompute W_c(x) = (1 + x)^c mod (x^K - 1) for distinct counts c.
    # This optimization reduces the number of poly_pow calls to at most K-1.
    distinct_counts = set(counts[1:])
    if 0 in distinct_counts:
        distinct_counts.remove(0)
    
    W_cache = {}
    for c in distinct_counts:
        P_init = [0] * K
        P_init[0] = 1
        P_init[1] = 1
        W_cache[c] = poly_pow(P_init, c, K, MOD)

    # Handle clubs with activity points divisible by K separately.
    # Each of the counts[0] clubs can either be included or not.
    if counts[0] > 0:
        factor = pow(2, counts[0], MOD)
        for j in range(K):
            dp[j] = (dp[j] * factor) % MOD

    # Handle other remainders r = 1, 2, ..., K-1.
    for r in range(1, K):
        c = counts[r]
        if c == 0:
            continue
        
        W_c = W_cache[c]
        # V_r(x) = (1 + x^r)^c mod (x^K - 1).
        # This is equivalent to replacing x with x^r in W_c(x) mod (x^K - 1).
        # Since (1 + x^r)^c = sum_{k=0}^c binom(c, k) x^{rk},
        # and W_c(x) = sum_{j=0}^{K-1} w_j x^j where w_j = sum_{k=j mod K} binom(c, k),
        # it follows that (1 + x^r)^c = sum_{j=0}^{K-1} w_j x^{rj mod K}.
        V_r = [0] * K
        for j in range(K):
            V_r[(j * r) % K] += W_c[j]
        # Modulo V_r coefficients as multiple j's might map to the same index.
        V_r = [v % MOD for v in V_r]
        
        # Combine the current possibilities with clubs of remainder r.
        dp = poly_mul(dp, V_r, K, MOD)

    # The result is dp[0] (total ways for sum = 0 mod K) minus 1 (to exclude the empty set).
    # Python's modulo operator handles negative results correctly.
    print((dp[0] - 1) % MOD)

if __name__ == '__main__':
    solve()

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