メモ

yukicoderでゆるふわgolf

A Sequence of Permutations

ほんまか？

a_{n}=a_{n-1}-a_{n-2} は a_{n}=a_{n-6} を満たすので、mod 6で見たいという気持ちで式変形をすると
a_n\\ = a_{n-1} a_{n-2}^{-1}\\ = a_{n-2} a_{n-3}^{-1} a_{n-2}^{-1} \\ = (a_{n-4} a_{n-5}^{-1} a_{n-4}^{-1}) (a_{n-5} a_{n-6}^{-1} a_{n-5}^{-1})^{-1} (a_{n-4} a_{n-5}^{-1} a_{n-4}^{-1})^{-1}\\ =(a_{n-4} a_{n-5}^{-1} a_{n-4}^{-1} a_{n-5}) a_{n-6} (\ldots)^{-1}
となって
a_{n-4} a_{n-5}^{-1} a_{n-4}^{-1} a_{n-5}\\ =(a_{n-5} a_{n-6}^{-1}) a_{n-5}^{-1} (a_{n-5} a_{n-6}^{-1})^{-1} a_{n-5}\\ = a_{n-5} a_{n-6}^{-1} a_{n-5}^{-1} a_{n-6}\\ = a_1 a_0^{-1} a_1^{-1} a_0 =:X
として
a_n = X a_{n-6} X^{-1}
を得る。よってO(N\log K)で解けた。

ところでなんでこれうまくいくんすかね。

例えばa_{n}=a_{n-1}a_{n-2}^{-1}a_{n-3}a_{n-4}^{-1}で同じ問題を考えると、同様にある定数 X により a_{n}=X a_{n-10} X^{-1}と書けるが、途中の計算は違っていて、例えば a_{n}=X(n) a_{n-5}^{-1} X(n)^{-1} とは書けない。

証明or反例を募集しています

20250226追記

a_1 a_0^{-1} a_1^{-1} a_0 のまま考えてしまったのが才能ナシで、 a_3 a_0 と書くと一般のケースが証明しやすいという話だったらしい。
一般に漸化式 a_n=a_{n-1}a_{n-2}^{-1}\ldots a_{n-2d}^{-1} で定まる数列を考える。
X(n):=a_n a_{n-2d-1} とおく。漸化式から任意の n で a_n^{-1} a_{n-1} a_{n-2}^{-1}\ldots a_{n-2d}^{-1}=\mathrm{id} であることに注意して
X(n) =a_n (a_{n-1}^{-1} a_{n-2} a_{n-3}^{-1}\ldots a_{n-2d-1}^{-1}) a_{n-2d-1}\\ =a_n a_{n-1}^{-1} a_{n-2} a_{n-3}^{-1}\ldots a_{n-2d}\\ =a_{n+1}a_{n-2d}=X(n+1)
より、 X(n) は n によらない定数。これを改めて X とおき a_n = X a_{n-2d-1}^{-1} = X a_{n-4d-2} X^{-1} を得る。