HHKB2020 E - Lamps (500)
あるマスが照らされないパターンは$ 2^{k - 隣接する散らかっていないマス数}
あるマスについて隣接する散らかっていないマスを愚直に求めると$ O(N^2) \times O(N) = O(N^3)
上下左右の方向でまとめてそれぞれ求めることで$ O(N^2)になる
累乗は$ 2^{HW}まで求めておく必要がある
求める答えは$ k 2^k - あるマスが照らされないパターンの和
累乗の計算、累積和の計算、各マスの照らされないパターンの計算がそれぞれ$ O(N^2)