概要

\(N\) 人の中から \(K\) 人を選ぶとき、その実力値の和が \(M\) の倍数になる組み合わせの数を求める問題です。

考察

この問題は単純にすべての組み合わせを試すと、\(_NC_K\) 通りとなり、最大で \(_{30}C_{15} \approx 1.5 \times 10^8\) 通りもあり、時間がかかりすぎてしまいます（TLE）。

しかし、実力値そのものではなく「\(M\) で割った余り」だけを考えれば十分です。なぜなら、和が \(M\) の倍数であるかどうかは、和を \(M\) で割った余りが \(0\) かどうかで決まるからです。つまり、各 \(A_i\) を \(A_i \bmod M\) に置き換えて考えることができます。

これを活用して、「半分全列挙」というテクニックを使います。配列を前半と後半の2つに分け、それぞれの部分について「選ぶ人数」と「その合計の \(M\) で割った余り」を全列挙します。そして、前半で \(k\) 人選んだときに和が \(s\) になる組み合わせ数を求めておけば、後半で \(K-k\) 人選んで和が \((-s) \bmod M\) になる組み合わせ数と掛け合わせることで、全体で和が \(0 \bmod M\) になる選び方が求められます。

アルゴリズム

1. 各実力値 \(A_i\) を \(A_i \bmod M\) に変換する。
2. 配列を前半 left と後半 right に分割する。
3. 各配列に対して、「選ぶ人数」ごとに「和の余り」およびその組み合わせ数を動的計画法で求める。
   • dp[cnt][sum] := cnt 個選んで和が sum (mod M) となる組み合わせ数
4. 前半で l_cnt 人選んだ場合、後半からは K - l_cnt 人選んで、和が (-l_sum) mod M となる組み合わせを探し、積を取って加算する。

計算量

• 時間計算量: \(O(N \cdot 2^{N/2})\)
• 空間計算量: \(O(2^{N/2} \cdot M)\)

※ 最悪ケースで \(N=30\) のとき、\(2^{15} = 32768\) 程度であり、十分高速に動作します。

実装のポイント

• 実力値を事前に \(M\) で割った余りに変換しておく。
• DP更新時にインデックスを逆順に回すことで、同じ要素を二重に使わないようにする。
• 和の余りが負にならないよう、(-l_sum) % M のように正規化する。

## ソースコード

```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()

この解説は qwen3-coder-480b によって生成されました。