メモ

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反例を募集しています