agc031_d A Sequence of Permutations
https://atcoder.jp/contests/agc031/tasks/agc031_d
https://img.atcoder.jp/agc031/editorial.pdf
Tutorial
对于排列 (p,q) 定义 (pq) 为一个第 (i) 个元素为 (p_{q_i}) 的排列,那么 (f(p,q)=pq^{-1})
- (a_1=p)
- (a_2=q)
- (a_3=qp^{-1})
- (a_4=qp^{-1}q^{-1})
- (a_5=qp^{-1}q^{-1}pq^{-1})
- (a_6=qp^{-1}q^{-1}p^2q^{-1})
- (a_7=qp^{-1}q^{-1}pqpq^{-1})
- (a_8=qp^{-1}q^{-1}pqp^{-1}qpq^{-1})
- (cdots)
观察发现同一元素被消去了许多次,尝试将 (a_i) 表示为 (A_iB_iA_i^{-1}) 的形式
- ((A_1,B_1)=(id,p))
- ((A_2,B_2)=(id,q))
- ((A_3,B_3)=(id,qp^{-1}))
- ((A_4,B_4)=(q,p^{-1}))
- ((A_5,B_5)=(qp^{-1},q^{-1}))
- ((A_6,B_6)=(qp^{-1},q^{-1}p))
- ((A_7,B_7)=(qp^{-1}q^{-1}p,p))
- ((A_8,B_8)=(qp^{-1}q^{-1}p,q))
- (cdots)
将 ((A_7,B_7)) 表示为这样的形式方便发现性质.
发现经过 (6) 次迭代后 ((A,p)) 和 ((A,q)) 变成了 ((Aqp^{-1}q^{-1}p,p)) 和 ((Aqp^{-1}q^{-1}p,q))
找到循环节后就很好,解决了.