コンテストへのリンク:■
コンテスト中AC:A〜D
D - I Hate Non-integer Number
数列の部分和に関する問題なので、部分和DPを考えます。
数列
の
項目までの部分和であって、和が
となるものの個数
今回は、何個選んだかも必要なので、情報を足します。
数列
の
項目までの部分和であって、部分和を構成する要素の数が
個、その和が
であるものの個数
今回、数列の要素数はと少ないですが、
であり、和のとりうる範囲が非常に大きく、上記のDPは使えません。
ここで、選ぶ要素数を固定し、個とします。
個の要素からなる部分和
の平均が整数となるためには、
が
の倍数である必要があります。すなわち、以下の条件を満たせばよいです。
つまり、部分和のだけわかれば、倍数となるかを判定できます。
そこで、以下のDPが考えられます。
数列
の
項目までの部分和であって、部分和を構成する要素の数が
個であり、その和を
とした時に
であるものの個数
このようにすれば、のとりうる範囲も
となり、
個に限定されます。
計算量は、DPテーブルを埋めるためにかかり、
のそれぞれについて計算する必要があるので、
だと思います。
実装はコンテスト後に見直ししたもの。
Submission #33697694 - AtCoder Beginner Contest 262