概要

各部活動を「選ぶ／選ばない」の部分集合のうち、活動ポイント合計が \(K\) の倍数になる（ただし空集合は除く）組み合わせ数を、\(10^9+7\) で数え上げる問題です。

考察

素朴に全ての選び方（\(2^N\) 通り）を列挙して合計を調べると、\(N\le 10^5\) では到底間に合いません。

ここで重要な観察は、「合計が \(K\) の倍数かどうか」は 合計そのものではなく \(K\) で割った余り（\(0\sim K-1\)）だけ分かれば十分 だということです。
つまり、これまでに選んだ部活動の合計の「余り」ごとに、何通りの選び方があるかを管理すれば、巨大な探索を避けられます。

例えば \(K=5\) のとき、ある時点で「合計の余りが \(2\) になる選び方が何通りあるか」さえ分かっていれば、新しい部活動（余り \(r\)）を追加したときに余りが \((2+r)\bmod 5\) に遷移することが分かります。

ただし「同じ部活動を1回の更新で何度も使ってしまう」ことを防ぐため、DP更新は 前の配列から新しい配列へ 作る必要があります（in-place 更新は重複カウントの原因）。

アルゴリズム

DP を次のように定義します。

• \(dp[j]\)：ここまで見た部活動からいくつか選んで、活動ポイント合計を \(K\) で割った余りが \(j\) になる選び方の数（\(\bmod\ 10^9+7\)）

初期状態は「空集合」だけが存在するので - \(dp[0]=1\)、それ以外は \(0\)

各部活動の活動ポイント \(a\) について、\(r=a\bmod K\) とします。
この部活動を「選ばない」場合は余りは変わらず、「選ぶ」場合は余りが \((j+r)\bmod K\) に変わります。

よって遷移は - 選ばない：\(newdp[j] \mathrel{+}= dp[j]\) - 選ぶ：\(newdp[(j+r)\bmod K] \mathrel{+}= dp[j]\)

を全ての \(j\) について行います。

最後に欲しいのは「合計が \(K\) の倍数」つまり余り \(0\) の個数ですが、問題では空集合が禁止なので - 答え \(= dp[0]-1\)（空集合の分を引く）

具体例

\(K=3\)、\(A=[1,2]\) のとき： - 初期：\(dp=[1,0,0]\)（空集合のみ） - \(1\) を処理（\(r=1\)）
- 空集合から「選ぶ」と余り \(1\) が1通り増える
→ \(dp=[1,1,0]\) - \(2\) を処理（\(r=2\)）
- 余り \(0\)（空）から「選ぶ」→余り \(2\) が増える
- 余り \(1\)（{1}）から「選ぶ」→余り \((1+2)\bmod 3=0\) が増える（{1,2}）
→ \(dp=[2,1,1]\)

このとき余り \(0\) は2通り（空集合と {1,2}）なので、空集合を除いて答えは \(2-1=1\) 通りです。

計算量

• 時間計算量: \(O(NK)\)（各部活動ごとに余り \(0\sim K-1\) を更新）
• 空間計算量: \(O(K)\)（余りごとの個数だけ保持）

実装のポイント

• 空集合を \(dp[0]=1\) として入れておき、最後に \(-1\) して除外します。

• 1つの部活動を同じ更新中に複数回使わないために、newdp = dp[:] のように 配列をコピーしてから遷移します（in-place 更新は不可）。

• \(K=1\) のときは全ての非空部分集合が条件を満たすため、答えは \(2^N-1\) を高速に計算できます（コードでも早期リターンしています）。

• 遷移のたびに \(10^9+7\) での剰余を取り、オーバーフローや巨大数化を防ぎます。

  ソースコード

import sys

MOD = 10**9 + 7

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

    if K == 1:
        print((pow(2, N, MOD) - 1) % MOD)
        return

    dp = [0] * K
    dp[0] = 1  # empty subset

    for a in A:
        r = a % K
        newdp = dp[:]  # not taking this club
        for j in range(K):
            v = dp[j]
            idx = j + r
            if idx >= K:
                idx -= K
            x = newdp[idx] + v
            if x >= MOD:
                x -= MOD
            newdp[idx] = x
        dp = newdp

    ans = dp[0] - 1  # exclude empty subset
    if ans < 0:
        ans += MOD
    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。