ABC 401-500/ABC455F - Merge Slimes 2 - 競技プログラミング用 知識集積所

---

問題

ABC455F

必要知識

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

• lazy segment木※
• 剰余類換※

考え方

まず、指定の重さのスライムたちが合体する場合のコストの最小値を考える必要がある。

重さA,B,Cの3つのスライムが合体するときで考えてみる。
AとBが先に合体すると、1回目の合体のコストがAB、2回目が(A+B)C、合計AB+BC+CA。
BとC、CとAが先に合体しても同じ。
つまり、どの順で合体してもコストは同じであり、異なるスライム2つの重さの積の総和である。

4つ合体するときも同様。
A,B,Cの3つが先に合体して後からDを合体すると、AB+BC+CA+D(A+B+C)。
A,Bの合体とC,Dの合体を合体すると、AB+CD+(A+B)(C+D)。
どちらも展開すると同じであり、異なるスライム2つの重さの積の総和である。

スライムが何体になってもこの法則は同様（証明略）であり、任意の合体順で必ず最小値になる。
つまり、この合体は交換法則や結合法則が成り立つモノイドである。
従って、このスライムをlazy segment木※に乗せることができる。

重さの加算のコストへの反映が少し難しいが、M体合体でそれぞれf増やした後のコストは

(a+f)(b+f) = ab + (a+b)f + f^2

の形のM(M-1)/2個の総和と考えると、元のコストとの差分は

• 全スライムの元の重さ合計×自分以外のスライムの個体数(M-1)×増加量f
• スライムAがf増加した後スライムBがf増加するときの相乗効果f^2がM(M-1)/2回分

である。
ここに個体数が必要なので、lazy segment木※には「個体数、重さ、コスト」の3つを乗せること。

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

解答例

解答例

注意点

long long型を使用する。

10^9規模の値をたくさん足すので、int型からはみ出る。
答えはもちろん、途中の重さなどについてもlong long型を用いること。

別解