E - Cheating Amidakuji Editorial by kyopro_friends


この問題のように「1つだけ操作を飛ばしたときの結果を求める」という類の問題に対しては、一般に、前後からの”累積和”を求めるアプローチが有効なことが多くあります。(高度ですが、逆元を要求しない全方位木DPが典型的な例です)

\(k\) について「k番目までの操作をしたときの結果」と「k番目以降の操作をしたときの結果」を求めておき、結果を合体させます。詳細は下図を参考にしてください。

posted:
last update: