CODE THANKS FESTIVAL 2018:E - Union
問題
解法
dp(i, j) := 整数 i が j 個あるとき,これから黒板に書かれている数を1つにする通り数
と DP を定義する.このとき,
dp(i, j) = dp(i + 1, (j + k) / 2)
(k は 0 <= k <= a_i で (j + k) % 2 == 0 を満たす整数)
と漸化式が立つ.i が T を超えた場合,上の漸化式だと愚直に / 2 していく形になって虚無なので,その時の j が2の累乗数であれば 1 通り,そうでなければ 0 通りとして枝刈りしてしまえばよい.O(T * 300^2).
解答
計算量的には枝刈りは必要なかったが,実装上したほうが楽だと思った.