欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

牛客多校2 - Just Shuffle(置换群的幂)

程序员文章站 2022-07-08 10:16:51
题意给出一个置换 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=BA^k=B ,k 是一个大质数
思路
基础知识(1)
基础知识(2)
了解置换群概念以及基本性质后,开始讲解此题。
Ak=B=>(Ak)t=Bt=>Akt=Bt(kt%r)=1kt1(%r),Akt=A()=Bttkt1(%r)gcd(k,r)=1=>t=>exgcdtt<0+rBt?A^k=B\\=>({A^k})^t = B^t=>A^{kt}=B^t\\如果(kt\%置换群秩r)=1即kt ≡ 1(\%r),那么A^{kt} = A(置换群)=B^t\\问题转为如和求解t?\\kt ≡ 1(\%r)又gcd(k, r) =1\\=>由数论知识,方程有解,所以t必然存在\\=>由exgcd即可求解t,如果t<0,则一直+r\\问题继续转化为如何求解B^t?
开始讲解:

B=(12344123) \begin{gathered} B=\begin{pmatrix} 1 & 2&3&4 \\ 4&1&2 & 3 \end{pmatrix} \end{gathered}
B2=(12344123)(12344123)=(12343412) \begin{gathered} B^2=\begin{pmatrix}1 & 2&3&4 \\ 4&1&2 & 3 \end{pmatrix}*\begin{pmatrix}1 & 2&3&4 \\ 4&1&2 & 3 \end{pmatrix}=\begin{pmatrix}1 & 2&3&4 \\ 3&4&1 & 2 \end{pmatrix} \end{gathered}

B3=B2B=(12343412)(12344123)=(12342341) \begin{gathered} B^3=B^2*B=\begin{pmatrix}1 & 2&3&4 \\ 3&4&1 & 2\end{pmatrix}*\begin{pmatrix}1 & 2&3&4 \\ 4&1&2 & 3 \end{pmatrix}=\begin{pmatrix} 1&2&3&4\\2&3&4&1\end{pmatrix} \end{gathered}

=>BtBt=>B^t就相当于在B中的环走t步
t=3(12342341)举例\\t=3\\\begin{pmatrix}1 & 2&3&4 \\ 2&3&4 & 1 \end{pmatrix}
=1>4>3>2>131321223323构造=1->4->3->2->1走3步\\1走3步到2(1-2匹配),2走3步到3(2-3匹配)以此类推

cir[i]i(0<=i<size)cir[i]icir[(i+t)%size]itcir[i]cir[(i+t)%size]=>Ans[cir[i]]=cir[(i+t)%size]设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

相关标签: 2020年暑假集训