Overview

Given \(N\) club activities, select one or more of them. Find the number of combinations where the total activity points of the selected clubs is a multiple of \(K\).

Analysis

In this problem, we want to check for all subsets (excluding the empty set) whether the sum of their elements is a multiple of \(K\), and find the total number of such selections.

A naive approach would be to enumerate all subsets (\(2^N\) possibilities) and check whether each sum is a multiple of \(K\). However, this is completely infeasible for the constraint \(N \leq 10^5\) (\(2^{10^5}\) is astronomically large).

This is where dynamic programming (DP) comes in. Instead of dealing with the actual activity points \(A_i\), it suffices to consider only their “remainders when divided by \(K\).” This is because whether the sum is a multiple of \(K\) depends only on “whether the remainder of the sum divided by \(K\) is \(0\).”

Therefore, we define the following DP:

dp[r] := the total number of ways to select clubs such that the sum has remainder \(r\) when divided by \(K\)

In the initial state, no club has been selected yet, so we set dp[0] = 1 corresponding to the empty set (though we need to exclude the empty set at the end).

Then, for each activity point \(A_i\) in order, we transition from each existing state dp[r] to the new state dp[(r + A_i) % K].

For example, if currently dp[2] = 3, this means “there are 3 ways to select clubs such that the sum has remainder \(2\) when divided by \(K\).” If we add activity point \(A_i\), the new remainder of the sum becomes \((2 + A_i) \bmod K\). Thus, we update by adding 3 to dp[(2 + A_i) % K].

In this way, the final dp[0] stores “the total number of ways to select clubs such that the sum is a multiple of \(K\).” However, this includes the case of “selecting nothing,” so we subtract 1 at the end to get the answer.

Algorithm

1. Compute the remainder of each activity point \(A_i\) divided by \(K\).
2. Prepare a DP array dp and initialize with dp[0] = 1 (empty set).
3. For each \(A_i\):
   • Create a new DP array new_dp by copying the current one.
   • For each remainder \(r\), perform new_dp[(r + A_i) % K] += dp[r].
   • Update dp with new_dp.
4. Subtract 1 from the final dp[0] to get the answer (excluding the empty set).
5. Output the answer modulo \(10^9 + 7\).

Complexity

• Time complexity: \(O(NK)\)
• Space complexity: \(O(K)\)

For each activity point, we update \(K\) entries of the DP table, so the total time is \(O(NK)\). The space is \(O(K)\) for the DP table alone.

Implementation Notes

• By using A_i % K instead of the activity points themselves, we can reduce computation.
• During DP updates, use a separate array (new_dp) to avoid updating values in-place (i.e., copy first).
• Don’t forget to subtract the empty set at the end.
• Handle the result properly with (dp[0] - 1) % MOD to ensure the answer does not become negative.

## Source Code

```python
MOD = 10**9 + 7

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:]))

    # DPテーブル: dp[r] = 和をKで割った余りがrとなる部分集合の個数
    dp = [0] * K
    dp[0] = 1  # 空集合に対応（ただし後で引く）

    for a in A:
        a_mod = a % K
        new_dp = dp[:]
        for r in range(K):
            new_r = (r + a_mod) % K
            new_dp[new_r] = (new_dp[new_r] + dp[r]) % MOD
        dp = new_dp

    # 空集合を除くので dp[0] から1を引く
    result = (dp[0] - 1) % MOD
    print(result)

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.