题意给出一个置换 B,求出一个置换 A ,使得Ak=BA^k=BAk=B ,k 是一个大质数思路基础知识(1)基础知识(2)了解置换群概念以及基本性质后,开始讲解此题。Ak=B=>(Ak)t=Bt=>Akt=Bt如果(kt%置换群秩r)=1即kt≡1(%r),那么Akt=A(置换群)=Bt问题转为如和求解t?kt≡1(%r)又gcd(k,r)=1=>由数论知识,方程有解,所以t必然存在=>由exgcd即可求解t,如果t<0,则一直+r问题继续转化为如何求解Bt?A^...
题意
给出一个置换 B,求出一个置换 A ,使得Ak=B ,k 是一个大质数
思路
基础知识(1)
基础知识(2)
了解置换群概念以及基本性质后,开始讲解此题。
Ak=B=>(Ak)t=Bt=>Akt=Bt如果(kt%置换群秩r)=1即kt≡1(%r),那么Akt=A(置换群)=Bt问题转为如和求解t?kt≡1(%r)又gcd(k,r)=1=>由数论知识,方程有解,所以t必然存在=>由exgcd即可求解t,如果t<0,则一直+r问题继续转化为如何求解Bt?
开始讲解:
B=(14213243)
B2=(14213243)∗(14213243)=(13243142)
B3=B2∗B=(13243142)∗(14213243)=(12233441)
=>Bt就相当于在B中的环走t步
举例t=3(12233441)
构造=1−>4−>3−>2−>1走3步1走3步到2(1−2匹配),2走3步到3(2−3匹配)以此类推
设cir[i]表示存储圆上的第i个点(0<=i<size)cir[i]−−−环上第i个点的值cir[(i+t)%size]−−−环上第i个点顺时针走t步到达位置的值因此cir[i]−−cir[(i+t)%size]匹配=>Ans[cir[i]]=cir[(i+t)%size]
AC代码
本文地址:https://blog.csdn.net/weixin_44412226/article/details/107395789