概要

\(N\) 個の部活動から \(1\) つ以上を選び、活動ポイントの合計が \(K\) の倍数となる選び方の総数を求める問題です。動的計画法（DP）を用いて、合計を \(K\) で割った余りごとに場合の数を管理します。

考察

素朴なアプローチの問題点

\(N\) 個の部活動から \(1\) つ以上選ぶ方法は全部で \(2^N - 1\) 通りあります。\(N\) が最大 \(10^5\) なので、すべての組み合わせを列挙すると \(2^{100000}\) 通りとなり、とても間に合いません。

重要な気づき

問題で求められているのは「合計が \(K\) の倍数」という条件です。ここで重要なのは、合計そのものではなく、合計を \(K\) で割った余りだけが重要 ということです。

\(K\) は最大 \(100\) と小さいので、余りは \(0, 1, 2, \ldots, K-1\) の \(K\) 通りしかありません。この性質を利用して、余りごとに選び方の数を管理する DP を考えます。

DPの状態設計

\(dp[j]\) = 「選んだ部活動の活動ポイントの合計を \(K\) で割った余りが \(j\) となる選び方の数」

と定義します。初期状態として、何も選ばない場合（合計 \(0\)）を考え、\(dp[0] = 1\) とします。

アルゴリズム

各部活動 \(a\) について、「選ぶ」か「選ばない」かの 2 択を考えます。

1. 初期化: \(dp[0] = 1\)（何も選ばない状態）、それ以外は \(0\)
2. 遷移: 各部活動 \(a\) に対して、現在の \(dp\) から新しい \(dp\) を計算
   • 選ばない場合: \(new\_dp[j] \mathrel{+}= dp[j]\)
   • 選ぶ場合: \(new\_dp[(j + a) \mod K] \mathrel{+}= dp[j]\)
3. 答えの計算: 最終的な \(dp[0]\) から、何も選ばない場合（\(1\) 通り）を引く

具体例

\(N = 3\), \(K = 3\), \(A = [1, 2, 3]\) の場合を考えます。

• 初期: \(dp = [1, 0, 0]\)（何も選ばない：余り \(0\)）
• \(a = 1\) を処理後: \(dp = [1, 1, 0]\)
  • 選ばない：余り \(0\) のまま
  • 選ぶ：余り \(0 + 1 = 1\)
• \(a = 2\) を処理後: \(dp = [1, 1, 1] + [0, 1, 1] = [1, 2, 2]\)
• \(a = 3\) を処理後: 余り \(0\) となる組み合わせが \(4\) 通り

最後に何も選ばない \(1\) 通りを引いて、答えは \(4 - 1 = 3\) となります。 （実際に \(\{3\}, \{1,2\}, \{1,2,3\}\) の \(3\) 通り）

計算量

• 時間計算量: \(O(NK)\)
  • 各部活動について、\(K\) 個の状態を更新するため
• 空間計算量: \(O(K)\)
  • DP 配列のサイズが \(K\)

\(N = 10^5\), \(K = 100\) のとき、\(10^7\) 程度の計算量となり、十分高速です。

実装のポイント

• 各 \(A_i\) は最大 \(10^9\) と大きいですが、\(K\) で割った余りのみを使うので、最初に \(a \mod K\) を計算しておきます

• 答えが非常に大きくなるため、計算の途中で \(10^9 + 7\) で割った余りを取ります

• 最後に \(1\) を引くとき、負の数になる可能性を考慮して (dp[0] - 1) % MOD とします（Python では負の余りも正しく処理されます）

• 遷移時に new_dp を作成することで、同じ部活動を複数回選んでしまうミスを防げます

  ソースコード

def solve():
    MOD = 10**9 + 7
    
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    # dp[j] = 選んだ部活動の活動ポイントの合計を K で割った余りが j となる選び方の数
    # 空の組み合わせも含めてカウント
    dp = [0] * K
    dp[0] = 1  # 何も選ばない場合
    
    for a in A:
        r = a % K
        new_dp = [0] * K
        for j in range(K):
            # この部活動を選ばない場合
            new_dp[j] = (new_dp[j] + dp[j]) % MOD
            # この部活動を選ぶ場合
            new_dp[(j + r) % K] = (new_dp[(j + r) % K] + dp[j]) % MOD
        dp = new_dp
    
    # dp[0] には何も選ばない場合（合計0）も含まれているので、1を引く
    ans = (dp[0] - 1) % MOD
    print(ans)

solve()

---

この解説は claude4.5opus によって生成されました。