ABC 401-500/ABC457F - Second Gap - 競技プログラミング用 知識集積所

---

問題

ABC457F

必要知識

B以下レベルの内容は省略

• 挿入DP※
  • 動的計画法
• lazy segment木※
• 剰余類環

考え方

※逆向きの方が考えやすかったので、ここではDを逆順にして、(P[1],P[2],……,P[i+1])でのトップ2の距離として問題を解いている。

先頭k個を1からkまでの順列にして、D[1]からD[k-1]までを満たすパターン数を、トップ位置ごとに数える。
先頭k+1個を1からk+1までの順列にする話を考えるとき、

• k+1番目がk+1であるものは、追加前でのそのD[k]個前がトップだった個数に等しい（トップはk+1番目の方）
• k+1番目がkであるものも、追加前でのそのD[k]個前がトップだった個数に等しい（トップはD個前の方）
  • D[k]個前のkをk+1に押し上げたと考える
• k+1番目がk-1以下であるものは、
  • Dの値が前から変わらなければ、各トップのもの1つに対してk-1個ずつある
    • 最後に足す値以上だったところを全て+1押し上げたと考える
  • Dの値が前から変わっていれば、存在しない

という形で情報を更新していけばよい。
最終的に、全体の総和が答えとなる。

問題は、この更新を普通にやると計算量があふれる点。
やることは全体への範囲乗算、1点への加算、全体の総和の3つなので、lazy segment木※を使って情報を整理するとよい。

答えは998244353で割った余りを要求されているので、剰余類環の考えに従って処理する。

解答例

解答例

注意点

別解