第三回日本最強プログラマー学生選手権-予選- (AtCoder Beginner Contest 262) D - I Hate Non-integer Number (400)
$ 2^n-1パターンを愚直に求めるのは$ \mathcal{O}(N2^N)で間に合わない
選ぶ個数を固定して$ m とすると和が$ m で割り切れるかどうかで判定ができるようになるので、$ dp[i][j][k] で$ i 番目まで見て$ j 個選んで余りが$ k の時の個数を$ m毎に求める
それぞれについて最後まで見て調度の数を選んだときの余りが$ 0の時の場合の数の和が答え
それぞれの$ iについてそれ以前の$ i,j,kからの遷移があるので$ \mathcal{O}(N^4)