HOJ 1529 - Red Black Balls

問題URL

問題概要

個のボールがあり、番目のボールには整数が書かれている。
これらのボールを青または赤で塗るとき、青いボールの値の総和が赤いボールの値の総和と等しくなる塗り分け方をで割った余りを求めよ。

制約

• 
• 

解説

値の総和が等しくなるということは、青の総和赤の総和です。
そのため、全体の総和が奇数の場合答えはです。そうでない場合、を番目のボールまでを塗り分けたとき、青の総和がとなるような選び方の総数とした動的計画法で答えを求めることができます。
よってこの問題は計算量で解くことができました。