Overview

This problem asks us to select one or more clubs and find the number of combinations where the total activity points are a multiple of K.

Analysis

This problem is a variant of the subset sum problem, where we count combinations whose total is a multiple of K. A naive approach would be to enumerate all subsets (\(2^N\) possibilities) and check whether each total is a multiple of K, but since N can be up to \(10^5\), enumerating \(2^{100000}\) subsets is computationally infeasible.

The key observation is that K is relatively small, at most 100. Instead of tracking the total value itself, we only need to manage the remainder when the total is divided by K, which drastically reduces the number of states.

Algorithm

We use dynamic programming (DP). We define a DP array of size K, where dp[j] represents the number of combinations such that the total points of the selected clubs has a remainder of j when divided by K.

For each club, we compute the remainder r of its activity points modulo K, and update new states from the current DP states. Specifically, for each remainder j, we add the current number of combinations to the position (j + r) % K.

As the initial state, we set the empty selection (remainder 0) to 1. At the end, we subtract 1 from dp[0] to exclude the empty set (the case where nothing is selected).

Complexity

• Time complexity: \(O(N \times K)\)
• Space complexity: \(O(K)\)

Since N is at most \(10^5\) and K is at most 100, this requires \(10^5 \times 100 = 10^7\) operations, which is feasible within the time limit.

Implementation Notes

• A DP array of size K is sufficient

• At each step, copy the current DP array before updating (to prevent state overwriting due to in-place updates)

• Properly apply modular arithmetic with \(10^9 + 7\)

• Don’t forget to subtract the empty set at the end

  Source Code

MOD = 10**9 + 7

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:2+n]))
    
    dp = [0] * K
    dp[0] = 1
    
    for a in A:
        r = a % K
        new_dp = dp[:]
        for j in range(K):
            if dp[j] > 0:
                new_r = (j + r) % K
                new_dp[new_r] = (new_dp[new_r] + dp[j]) % MOD
        dp = new_dp
    
    print((dp[0] - 1) % MOD)

if __name__ == '__main__':
    main()

This editorial was generated by deepseekv3.