問題

考え方

部分和問題に帰着する。 $a_i$ のうちいくつか選んだときにその和の $mod$ が $L$ に等しくなれば良い。 $mod$ 上で考えればよいので DP を回す最大値は $M$ 未満まででよい。

そのとき以下のように DP を定義する。

$dp[i][j] :=\ i$ 番目まで見たときの $j$ にいるときの最小回数

DPの初期値は $j=0$ の場合に $1$ で、DP遷移は $\displaystyle dp[i+1][j+a[i]] = min(dp[i+1][j+a[i]],\ dp[i][j] + \frac{j+a[i]}{M})$ となる。

$mod\ M$ で考えて良いので、DPを回す最大値は $M$ 未満でよかった。

ビット上で考えうる部分和を列挙したのち、 $i (mod\ M) = L$ なる $i$ ビット目がたっている場合には YES そうでない場合は NO と考えたが、その場合は (たぶんビット演算が重くて) TLE した。

mod M 上の最大値は M-1