ABC179 D - Leaping Tak (400)
$ dp[i
]としてi番目に到達する場合の数とすると、遷移がN個起こりうるので
$ O(N^2)
になりTLEする
区間が
$ K
個なので、BITで遷移を区間毎にまとめて行う
1区間の場合の数の和を求めるのを
$ O(\log N)
全ての点で全ての区間で行うので全体で
$ O(NK \log N)
問題:
https://atcoder.jp/contests/abc179/tasks/abc179_d
提出:
https://atcoder.jp/contests/abc179/submissions/16870371
#ABC179
#400pt
#D
#ABC
#AtCoder