Overview

Given \(N\) people, we want to find the number of ways to choose \(K\) people such that the sum of their skill values is a multiple of \(M\).

Analysis

If we naively try all combinations, there are \(_NC_K\) possibilities, which can be up to \(_{30}C_{15} \approx 1.5 \times 10^8\) — too many to enumerate in time (TLE).

However, it suffices to consider only the “remainder when divided by \(M\)” rather than the actual skill values. This is because whether the sum is a multiple of \(M\) is determined by whether the remainder of the sum divided by \(M\) is \(0\). In other words, we can replace each \(A_i\) with \(A_i \bmod M\).

Using this insight, we apply a technique called “meet in the middle.” We split the array into two halves (front and back), and for each half, we enumerate all possible pairs of “number of people chosen” and “remainder of their sum modulo \(M\).” Then, if we precompute the number of combinations where choosing \(k\) people from the first half gives a sum of \(s\), we can multiply it by the number of combinations where choosing \(K-k\) people from the second half gives a sum of \((-s) \bmod M\). This way, we can count all selections whose total sum is \(0 \bmod M\).

Algorithm

1. Convert each skill value \(A_i\) to \(A_i \bmod M\).
2. Split the array into the first half left and the second half right.
3. For each half, use dynamic programming to compute the number of combinations for each “number of people chosen” and “remainder of the sum.”
   • dp[cnt][sum] := number of combinations choosing cnt items with sum equal to sum (mod M)
4. For each case where l_cnt people are chosen from the first half, find the combinations from the second half that choose K - l_cnt people with sum equal to (-l_sum) mod M, multiply the counts, and add to the answer.

Complexity

• Time complexity: \(O(N \cdot 2^{N/2})\)
• Space complexity: \(O(2^{N/2} \cdot M)\)

※ In the worst case when \(N=30\), \(2^{15} = 32768\), which is fast enough.

Implementation Notes

• Pre-convert skill values to their remainders modulo \(M\).
• When updating the DP, iterate indices in reverse order to avoid using the same element twice.
• Normalize (-l_sum) % M to ensure the remainder 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])
    M = int(data[2])
    A = list(map(int, data[3:3+N]))
    
    # 実力値をMで割った余りに変換
    A_mod = [a % M for a in A]
    
    # 半分全列挙のために前半と後半に分割
    mid = N // 2
    left = A_mod[:mid]
    right = A_mod[mid:]
    
    # 左側のすべての部分集合について、要素数と合計(mod M)を計算
    from collections import defaultdict
    
    def enumerate_sums(arr):
        dp = [defaultdict(int) for _ in range(len(arr)+1)]
        dp[0][0] = 1
        for i in range(len(arr)):
            for cnt in range(i+1, -1, -1):
                for s in list(dp[cnt].keys()):
                    dp[cnt+1][(s + arr[i]) % M] = (dp[cnt+1][(s + arr[i]) % M] + dp[cnt][s]) % MOD
        return dp
    
    left_dp = enumerate_sums(left)
    right_dp = enumerate_sums(right)
    
    result = 0
    for l_cnt in range(len(left_dp)):
        r_cnt = K - l_cnt
        if r_cnt < 0 or r_cnt >= len(right_dp):
            continue
        for l_sum in left_dp[l_cnt]:
            needed_r_sum = (-l_sum) % M
            if needed_r_sum in right_dp[r_cnt]:
                result = (result + left_dp[l_cnt][l_sum] * right_dp[r_cnt][needed_r_sum]) % MOD
                
    print(result)

if __name__ == "__main__":
    main()

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