JAG Summer Camp 2013 Day 2 G - Perm Query

• 問題
• AC

与えられた置換$p$を巡回置換の合成$\sigma_1\sigma_2 ... \sigma_k$に分解して、ある巡回置換$\sigma$に注目する。$\sigma$の長さが$d$とすると、

• 列$\sigma x$の区間$[l, r]$の総和
• 列$\sigma^2 x$の区間$[l, r]$の総和
• ...
• 列$\sigma^d x = x$の区間$[l, r]$の総和

をすべて足せばこの巡回置換を一周した場合の総和が求まることになる。この際、巡回置換に現れるすべての数は同じ回数だけ$[l ,r]$に現れるので、上の総和は巡回置換に登場する数の総和の倍数になっている。

また、問題のようにすべての巡回置換を同時に適用した場合、次にもとに戻るのは（区間$[l, r]$に登場する）すべての巡回置換の長さの最小公倍数である。これを$\operatorname{LCM}(l, r)$とすると、$\operatorname{LCM}(l, r)$回の操作を行う場合、長さ$d$の巡回置換については$\operatorname{LCM}(l, r)/d$周することになる。この際、巡回置換に登場する数で最初に区間$[l, r]$に含まれていたものが$q$個であるとすると、巡回置換に登場する数はそれぞれ$q\operatorname{LCM}(l, r)/d$回足されることになる。

---

実装で迷った末に、Moのアルゴリズムを使った。

区間$[l, r]$についての値がわかっているとき、$[l, r+1]$の値を考える。まず、区間が伸びたことによって操作回数が$\operatorname{LCM}(l, r)$から$\operatorname{LCM}(l, r+1)$に伸びるので、既存の値が$\operatorname{LCM}(l, r+1)/\operatorname{LCM}(l, r)$倍になる。また、位置$r+1$が追加されるので、この位置を含む巡回置換$\sigma$の長さ$d$について、$(巡回置換 \sigma に登場する数の総和) \times \operatorname{LCM}(l, r+1)/d$が加算されることになり、新しい値が求まる。区間が縮む場合も同様に書ける。

$\operatorname{LCM}(l, r)$の値を得るのにsparse tableが使えるから計算量の問題はないと思って書き出したのだが、伸縮の際にmodの割り算が必要になるので結局$\log$がついて${O}(N \sqrt{Q} \log N)$だった。^[1]

---

lcmと同時に、それぞれの巡回置換の総和もセグメント木で持てばよいらしい。それはそうか……

---

1. lcmの範囲が大きいので逆数のテーブルは用意できない。でも、うまい方法がありそうな気もする。 ↩︎