Overview

This problem asks us to select \(K\) students from \(N\) students such that the sum of their ability values is a multiple of \(M\), and count the number of such selections. We solve this efficiently using Meet in the Middle (half enumeration).

Analysis

Problems with the Naive Approach

Consider examining all combinations of choosing \(K\) people from \(N\) people. The number of combinations is \(\binom{N}{K}\), which can be as large as \(\binom{30}{15} \approx 1.5 \times 10^8\). Furthermore, computing the sum for each combination results in an overall complexity of \(O(2^N \cdot N)\), which is very likely to cause TLE (Time Limit Exceeded).

Key Insight

The constraint \(N \leq 30\) suggests “Meet in the Middle.” While \(2^{30} \approx 10^9\) is too large, \(2^{15} \approx 3 \times 10^4\) can be processed fast enough.

Solution Strategy

Divide the students into two groups: a first half and a second half. For each group, enumerate all subsets and record “how many people were selected” and “the remainder of the sum divided by \(M\).” Then, combine the results from both groups to count the selections where exactly \(K\) people are chosen and the total sum is a multiple of \(M\).

Algorithm

1. Group Division: Split the \(N\) students into the first half (\(\lfloor N/2 \rfloor\) students) and the second half (the rest)

2. Subset Enumeration: For each group, enumerate all subsets and record the following:

   • The number of selected people \(k\)
   • The remainder \(r\) of the sum of ability values divided by \(M\)
   • The count of such subsets

3. Combining Results: Consider combinations where \(k_1\) people are chosen from the first half and \(k_2 = K - k_1\) people from the second half

   • When the first half has remainder \(r_1\), if the second half has remainder \(r_2 = (M - r_1) \mod M\), then the total sum is a multiple of \(M\)
   • Multiply and accumulate the counts of combinations that satisfy the condition

Concrete Example

For \(N=4, K=2, M=3, A=[1,2,3,4]\): - Split into first half \([1,2]\) and second half \([3,4]\) - Selecting 1 person from the first half: \((1, \text{remainder } 1), (1, \text{remainder } 2)\), each with 1 way - Selecting 1 person from the second half: \((1, \text{remainder } 0), (1, \text{remainder } 1)\), each with 1 way - For \(k_1=1, k_2=1\), count combinations where the sum of remainders is a multiple of \(M\) - First half remainder 1 × Second half remainder 2 → no match - First half remainder 2 × Second half remainder 1 → no match - And so on, checking all patterns

Complexity

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

  • Enumerate \(2^{N/2}\) subsets for each group
  • The combining step depends on the number of subsets, but is at most around \(O(2^{N/2} \cdot 2^{N/2} / M)\)
  • For \(N=30\), approximately \(2 \times 2^{15} \approx 6 \times 10^4\) enumerations

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

  • Subset information for each group is stored in a dictionary

Implementation Notes

• Enumeration using bitmasks: Each bit of mask represents whether an element is selected or not

• Using dictionaries: result[k][r] manages the number of ways to “select \(k\) people with remainder \(r\)”

• Complement calculation for remainders: The condition for the total to be a multiple of \(M\) is \(r_1 + r_2 \equiv 0 \pmod{M}\), i.e., \(r_2 = (M - r_1) \mod M\)

• Modulo \(10^9+7\): Since the answer can become very large, take the modulus at every multiplication and addition

  Source Code

import sys
from collections import defaultdict

def solve():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    M = int(input_data[2])
    A = [int(input_data[3 + i]) for i in range(N)]
    
    MOD = 10**9 + 7
    
    # Meet in the middle approach
    # Split N people into two halves
    half = N // 2
    left = A[:half]
    right = A[half:]
    
    # For left half: enumerate all subsets
    # Store (count of people, sum mod M) -> number of ways
    def enumerate_subsets(arr):
        n = len(arr)
        # result[k][r] = number of subsets with k people and sum % M == r
        result = defaultdict(lambda: defaultdict(int))
        for mask in range(1 << n):
            cnt = 0
            total = 0
            for i in range(n):
                if mask & (1 << i):
                    cnt += 1
                    total += arr[i]
            result[cnt][total % M] += 1
        return result
    
    left_subsets = enumerate_subsets(left)
    right_subsets = enumerate_subsets(right)
    
    ans = 0
    
    # Combine: choose k1 from left, k2 from right where k1 + k2 = K
    # sum1 + sum2 ≡ 0 (mod M) => sum2 ≡ -sum1 (mod M)
    
    for k1 in range(K + 1):
        k2 = K - k1
        if k1 > len(left) or k2 > len(right):
            continue
        if k2 < 0:
            continue
        
        left_dict = left_subsets[k1]
        right_dict = right_subsets[k2]
        
        for r1, cnt1 in left_dict.items():
            # Need r2 such that (r1 + r2) % M == 0
            r2 = (M - r1) % M
            if r2 in right_dict:
                ans = (ans + cnt1 * right_dict[r2]) % MOD
    
    print(ans)

solve()

---

This editorial was generated by claude4.5opus.