問題概要
$N \ $個のボールがあり、$i \ $番目のボールには整数$ \ A_i \ $が書かれている。
これらのボールを青または赤で塗るとき、青いボールの値の総和が赤いボールの値の総和と等しくなる塗り分け方を$ \ 998244353 \ $で割った余りを求めよ。
制約
- $2 \leq N \leq 200$
- $0 \leq A_i \leq 200$
解説
値の総和が等しくなるということは、青の総和$ \ = \ $赤の総和$ \ = \frac{\sum A_i}{2} \ $です。
そのため、全体の総和が奇数の場合答えは$ \ 0 \ $です。そうでない場合、$DP[i][j] \ $を$ \ i \ $番目のボールまでを塗り分けたとき、青の総和が$ \ j \ $となるような選び方の総数とした動的計画法で答えを求めることができます。
よってこの問題は計算量$ \ O(N \sum A_i) \ $で解くことができました。
