ABC044 C - 高橋君とカード / Tak and Cards

問題
提出コード
CはDPのCですね！

解法

動的計画法を利用します。
数列のi番目までのうち、j個の要素を足した結果がkになるようなものの個数
とします。
すると、

右辺の左の項は、を使用しないパターン(1つ前の個数がそのまま引き継がれます)、右の項は、を使用したパターン(使用すると、が1つ増えるので、見るべき場所は1つ前になります)です。
答えがどこにあるかというと、平均がになるので、個数列の要素を選んでいるときは、和がになっていなければなりません。よって、
dp[n][j][j×A]
の和を求めれば、答えになります。