NOMURA プログラミングコンテスト2022 (AtCoder Beginner Contest 253) E - Distance Sequence (500)
$ dp[i][j] でi番目の値がjの時の条件を満たす場合の数とする
単純に実装するとある$ dp[i][j] を求めるのに$ \mathcal{O}(M)かかるので全体で$ \mathcal{O}(NM^2)になる
DPの遷移元が連続していることを利用する
ある$ dp[i] について累積和を求めておくと、上の遷移が$ \mathcal{O}(1)になり全体で$ \mathcal{O}(NM)になる