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