Overview

This problem asks us to select one or more from \(N\) club activities such that the sum of activity points is a multiple of \(K\), and find the total number of such selections. Using dynamic programming (DP), we manage the number of ways for each remainder when the sum is divided by \(K\).

Analysis

Problem with the Naive Approach

The total number of ways to select one or more from \(N\) club activities is \(2^N - 1\). Since \(N\) can be up to \(10^5\), enumerating all combinations would result in \(2^{100000}\) possibilities, which is far too many to handle.

Key Insight

The condition required by the problem is “the sum is a multiple of \(K\)”. The crucial observation here is that only the remainder when the sum is divided by \(K\) matters, not the sum itself.

Since \(K\) is at most \(100\), which is small, the remainder can only take \(K\) values: \(0, 1, 2, \ldots, K-1\). Using this property, we can design a DP that manages the number of selections for each remainder.

DP State Design

Define:

\(dp[j]\) = “the number of ways to select club activities such that the sum of activity points has remainder \(j\) when divided by \(K\)”

As the initial state, considering the case where nothing is selected (sum \(0\)), we set \(dp[0] = 1\).

Algorithm

For each club activity \(a\), we consider two choices: “select it” or “don’t select it”.

1. Initialization: \(dp[0] = 1\) (the state where nothing is selected), all others are \(0\)
2. Transition: For each club activity \(a\), compute a new \(dp\) from the current \(dp\)
   • Don’t select: \(new\_dp[j] \mathrel{+}= dp[j]\)
   • Select: \(new\_dp[(j + a) \mod K] \mathrel{+}= dp[j]\)
3. Computing the answer: Subtract the case where nothing is selected (\(1\) way) from the final \(dp[0]\)

Concrete Example

Consider the case \(N = 3\), \(K = 3\), \(A = [1, 2, 3]\).

• Initial: \(dp = [1, 0, 0]\) (nothing selected: remainder \(0\))
• After processing \(a = 1\): \(dp = [1, 1, 0]\)
  • Don’t select: remainder stays \(0\)
  • Select: remainder \(0 + 1 = 1\)
• After processing \(a = 2\): \(dp = [1, 1, 1] + [0, 1, 1] = [1, 2, 2]\)
• After processing \(a = 3\): the number of combinations with remainder \(0\) becomes \(4\)

Finally, subtracting the \(1\) way of selecting nothing, the answer is \(4 - 1 = 3\). (Indeed, the \(3\) valid selections are \(\{3\}, \{1,2\}, \{1,2,3\}\).)

Complexity

• Time complexity: \(O(NK)\)
  • For each club activity, we update \(K\) states
• Space complexity: \(O(K)\)
  • The DP array has size \(K\)

When \(N = 10^5\) and \(K = 100\), the computation is on the order of \(10^7\), which is sufficiently fast.

Implementation Notes

• Each \(A_i\) can be as large as \(10^9\), but since we only use the remainder when divided by \(K\), we compute \(a \mod K\) beforehand

• Since the answer can become extremely large, we take the remainder modulo \(10^9 + 7\) during computation

• When subtracting \(1\) at the end, we account for the possibility of a negative number with (dp[0] - 1) % MOD (in Python, negative remainders are handled correctly)

• By creating a new_dp during transitions, we prevent the mistake of selecting the same club activity multiple times

  Source Code

def solve():
    MOD = 10**9 + 7
    
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    # dp[j] = 選んだ部活動の活動ポイントの合計を K で割った余りが j となる選び方の数
    # 空の組み合わせも含めてカウント
    dp = [0] * K
    dp[0] = 1  # 何も選ばない場合
    
    for a in A:
        r = a % K
        new_dp = [0] * K
        for j in range(K):
            # この部活動を選ばない場合
            new_dp[j] = (new_dp[j] + dp[j]) % MOD
            # この部活動を選ぶ場合
            new_dp[(j + r) % K] = (new_dp[(j + r) % K] + dp[j]) % MOD
        dp = new_dp
    
    # dp[0] には何も選ばない場合（合計0）も含まれているので、1を引く
    ans = (dp[0] - 1) % MOD
    print(ans)

solve()

---

This editorial was generated by claude4.5opus.