ABC183 E Queen on Grid
$ dp_{i, j}
:= マス
$ (i, j)
まで移動する方法の数 としてDPをすることを考える. 愚直に遷移を書くと
$ O(HW(H + W))
となって間に合わない. そこで累積和を用いてDPを高速化する. 各行・各列・斜めについてのDPの和を持っておけばよい(斜めは1次元配列で持つなら
$ i - j
の値により管理可能だが, この値が負になることもあるので注意).
実装例:
https://atcoder.jp/contests/abc183/submissions/21498474