概要

複数の部活動から1つ以上を選び、活動ポイントの合計がKの倍数となる組み合わせの数を求める問題です。

考察

この問題は部分和問題の変種で、合計値がKの倍数となる組み合わせを数えるものです。素朴なアプローチとしては、全ての部分集合（\(2^N\)通り）を列挙して合計値がKの倍数かどうかをチェックする方法が考えられますが、Nが最大\(10^5\)となるため、\(2^{100000}\)通りは現実的な時間では計算できません。

重要な観察として、Kの値が最大100と比較的小さいことに注目します。合計値そのものではなく、合計値をKで割った余りだけを管理することで、状態数を大幅に削減できます。

アルゴリズム

動的計画法（DP）を用います。DP配列をサイズKで定義し、dp[j]はこれまでに選んだ部活動の合計ポイントをKで割った余りがjとなる組み合わせの数を表します。

各部活動について、その活動ポイントをKで割った余りrを計算し、現在のDP状態から新しい状態を更新します。具体的には、各余りjに対して、新しい余り (j + r) % K の位置に現在の組み合わせ数を加算します。

初期状態として、何も選んでいない状態（余り0）を1通りとし、最後に空集合（何も選ばない場合）を除外するためにdp[0]から1を引きます。

計算量

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

Nが\(10^5\)、Kが100なので、\(10^5 \times 100 = 10^7\)回の操作で済み、制限時間内に実行可能です。

実装のポイント

• DP配列のサイズはKで十分

• 各ステップで現在のDP配列をコピーしてから更新を行う（インプレース更新による状態の上書きを防ぐ）

• モジュロ演算\(10^9 + 7\)を適切に行う

• 最後に空集合分を引くことを忘れない

  ソースコード

MOD = 10**9 + 7

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:2+n]))
    
    dp = [0] * K
    dp[0] = 1
    
    for a in A:
        r = a % K
        new_dp = dp[:]
        for j in range(K):
            if dp[j] > 0:
                new_r = (j + r) % K
                new_dp[new_r] = (new_dp[new_r] + dp[j]) % MOD
        dp = new_dp
    
    print((dp[0] - 1) % MOD)

if __name__ == '__main__':
    main()

この解説は deepseekv3 によって生成されました。