Skip to content →

列に対する変な操作

AGC027E や ARC110E を一般化すると、任意の位数 n の群とその長さ m の元の列で O(m + n log(n)) で同じことができそうですね。

数列 a に対する変な操作 X が、 実は簡単な操作 S (例:階差、累積和)を行った a では、簡単な操作 Y(例:swap)に見えるという問題。\(SX = YS \Leftrightarrow S^{-1}YS = X\) だから簡単な操作で表せる共役な演算を見つけろという問題に言い換えられる。\(X, Y\) の位数は等しい。\(S, Y\) が置換を表しているとき、\(X\) のサイクル分解は、\(Y\) のサイクル分解の頂点ラベルを \(S\) で置換したグラフになる。

Published in データ構造

Comments

コメントを残す

メールアドレスが公開されることはありません。

CAPTCHA