コンテストへのリンク:■
コンテスト中AC:A〜D

D - I Hate Non-integer Number

数列の部分和に関する問題なので、部分和DPを考えます。

$dp[i][j]:=$ 数列 $A$ の $i$ 項目までの部分和であって、和が $j$ となるものの個数

今回は、何個選んだかも必要なので、情報を足します。

$dp[i][j][k]:=$ 数列 $A$ の $i$ 項目までの部分和であって、部分和を構成する要素の数が $j$ 個、その和が $k$ であるものの個数

今回、数列の要素数は $N\leq 100$ と少ないですが、 $1\leq a_i \leq 10^9$ であり、和のとりうる範囲が非常に大きく、上記のDPは使えません。

ここで、選ぶ要素数を固定し、 $X$ 個とします。
$X$ 個の要素からなる部分和 $S$ の平均が整数となるためには、 $S$ が $X$ の倍数である必要があります。すなわち、以下の条件を満たせばよいです。
$S\ mod\ X = 0$

つまり、部分和の $mod\ X$ だけわかれば、倍数となるかを判定できます。
そこで、以下のDPが考えられます。

$dp[i][j][k]:=$ 数列 $A$ の $i$ 項目までの部分和であって、部分和を構成する要素の数が $j$ 個であり、その和を $S$ とした時に $S\ mod\ X = k$ であるものの個数

このようにすれば、 $k$ のとりうる範囲も $0\leq k \leq N-1$ となり、 $N$ 個に限定されます。

計算量は、DPテーブルを埋めるために $O(N^3)$ かかり、 $X=1,2,\cdots ,N$ のそれぞれについて計算する必要があるので、 $O(N^4)$ だと思います。
実装はコンテスト後に見直ししたもの。
Submission #33697694 - AtCoder Beginner Contest 262