概要

\(N\) 個の部活動から1つ以上を選ぶとき、選んだ部活動の活動ポイントの合計が \(K\) の倍数になる組み合わせの数を求める問題。

考察

この問題では、すべての部分集合（ただし空集合を除く）について、その要素の和が \(K\) の倍数かどうかを判定し、そのような選び方の総数を求めたいです。

素朴な方法としては、すべての部分集合（\(2^N\) 通り）を全探索して、それぞれの和が \(K\) の倍数かどうかを調べる方法が考えられます。しかし、制約 \(N \leq 10^5\) に対しては到底無理です（\(2^{10^5}\) は天文学的）。

そこで登場するのが 動的計画法（DP） です。
各部活動の活動ポイント \(A_i\) そのものを扱うのではなく、「\(K\) で割った余り」だけを考えれば十分です。なぜなら、和が \(K\) の倍数であるかどうかは、結局のところ「和を \(K\) で割った余りが \(0\) かどうか」だけを見ればよいからです。

したがって、以下のようなDPを考えます：

dp[r] := 和を \(K\) で割った余りが \(r\) となるような選び方の総数

初期状態では、まだどの部活動も選んでいないと考えられるので、空集合に対応する dp[0] = 1 とします（ただし最後に空集合を除外する必要があります）。

次に、各活動ポイント \(A_i\) を順番に見て、既存の各状態 dp[r] から新しい状態 dp[(r + A_i) % K] に遷移させます。

例えば、現在 dp[2] = 3 だったとすると、これは「和を \(K\) で割った余りが \(2\) になる選び方が3通りある」という意味です。そこに活動ポイント \(A_i\) を追加すると、新たな和の余りは \((2 + A_i) \bmod K\) になります。これによって、dp[(2 + A_i) % K] に3を加えることで更新できます。

このようにして、最終的に dp[0] には「和が \(K\) の倍数になる選び方の総数」が格納されます。ただし、この中には「何も選ばない」場合も含まれているため、最後に1を引いて答えとします。

アルゴリズム

1. 各活動ポイント \(A_i\) を \(K\) で割った余りを計算する。
2. DP配列 dp を用意し、dp[0] = 1 （空集合）で初期化。
3. 各 \(A_i\) について：
   • 新しいDP配列 new_dp をコピーして作る。
   • 各余り \(r\) に対して、new_dp[(r + A_i) % K] += dp[r] を行う。
   • dp を new_dp で更新。
4. 最終的な dp[0] から1を引き、答えとする（空集合を除外）。
5. 答えを \(10^9 + 7\) で割った余りを出力。

計算量

• 時間計算量: \(O(NK)\)
• 空間計算量: \(O(K)\)

各活動ポイントに対して、\(K\) 個のDPテーブルを更新するので、全体で \(O(NK)\) 時間かかります。空間はDPテーブル分だけで \(O(K)\) です。

実装のポイント

• 活動ポイントそのものではなく、A_i % K を使うことで計算量を削減できる。
• DP更新時には、別の配列（new_dp）を使って同時に更新しないようにする（別名コピー）。
• 最後に空集合を引くことを忘れないこと。
• 答えが負にならないように、(dp[0] - 1) % MOD のように適切に処理する。

## ソースコード

```python
MOD = 10**9 + 7

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:]))

    # DPテーブル: dp[r] = 和をKで割った余りがrとなる部分集合の個数
    dp = [0] * K
    dp[0] = 1  # 空集合に対応（ただし後で引く）

    for a in A:
        a_mod = a % K
        new_dp = dp[:]
        for r in range(K):
            new_r = (r + a_mod) % K
            new_dp[new_r] = (new_dp[new_r] + dp[r]) % MOD
        dp = new_dp

    # 空集合を除くので dp[0] から1を引く
    result = (dp[0] - 1) % MOD
    print(result)

if __name__ == "__main__":
    main()

---

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