置换群的快速幂
在自学polya的时候用到了置换群求幂的循环节个数的问题,然后就看看了快速幂。
当然也就是《置换群快速幂运算研究与讨论》一文了。
嗯,确实写的不错。这篇文章中有一个题,是庆典的日期的问题,也就是poj 1282。
[算法分析](摘自《置换群快速幂运算 研究与讨论》)
由于每个房间的转盘上的数字都是 p 个,而且每年每个祭司都在不同房间,所以我们可以把这些房间中安置的转盘,转化成 p 个长度为 n 的置换。而每一年祭司本身的位置,也可以组成一个长度 n 的置换。
显然,第 i 年祭司的位置,就是第 i-1 年祭司的位置,与第 i 年转盘上数字代表的置换的连接。现在的问题是求一个最早的年份 y,使得那一年祭司的位置是单位置换。由于转盘上的置换是以 p 为周期的,所以我们枚举 y mod p=k。那么也就是说:
T1 ⋅ T2 ⋅ ...T p ⋅ T1 ⋅ T2 ⋅ ... ⋅ T p ⋅ ... ⋅ Tk −1 ⋅ Tk = e
由于连接运算满足结合律,所以:
T1 ⋅ T2 ⋅ ... ⋅ Tk ⋅ (Tk +1 ⋅ Tk + 2 ⋅ ... ⋅ T p ⋅ T1 ⋅ T2 ⋅ ... ⋅Tk ) ⋅ ... ⋅ (Tk +1 ⋅ Tk + 2 ⋅ ... ⋅ T p ⋅ T1 ⋅ T2 ⋅ ... ⋅ Tk ) =e
我们可以预先算出 THead = T1 ⋅ T2 ⋅ ... ⋅ Tk 和 TStep = Tk +1 ⋅ Tk + 2 ⋅ ...⋅ T p ⋅ T1 ⋅ T2 ⋅ ... ⋅ Tk ,那么上式就转为:
THead ⋅ (TStep )^ ( y − k ) / p = e (TStep )^ ( y − k ) / p = (THead ) ^−1
所以,当我们枚举了 y mod p=k 以后,问题就转化成了:
已知 2 个置换 TDeah = (THead )^-1 , TStep ,求一个最小的数 x=(y-k)/p 使 TStep^x =TDeah 。
如果 TStep 和 TDeah 都是一个循环,那根据上面的算法立即可以得到答案的最小值x,也可以知道,所有可行的答案的形式,都是x+kn的形式。那如果有多个循环的话,显然可以列出一系列形如x mod ni=xi的模线性方程组。解出这个方程组,就可以得到答案了。
#include<iostream> #include <stdio.h> #include <string.h> using namespace std; #define maxn 210 int a[maxn][maxn],b[maxn][maxn],c[maxn][maxn];//c表示Thead的逆即Tdeah int d1[maxn],d2[maxn]; int n,p; bool find(int w1[],int w2,int k,int &y,int &x) { int t=k;y=-1; if(t==w2)y=0; t=w1[k];x=1; while(t!=k) { if(t==w2)y=x; t=w1[t]; x++; } if(y==-1)return false; return true; } int extend_gcd(int a,int b,int &x,int &y) { if(b==0){x=1;y=0;return a;} int t=extend_gcd(b,a%b,y,x); y-=a/b*x; return t; } int solve(int r[],int a[],int n)//扩展欧几里德两两合并 { int rr=r[0],aa=a[0],x,y; for(int i=1;i<n;i++) { int tmp=r[i]-rr; int gcd=extend_gcd(aa,a[i],x,y); if(tmp%gcd!=0)return -1; int temp=a[i]/gcd; x=((tmp/gcd*x)%temp+temp)%temp; rr=rr+aa*x; aa=aa*a[i]/gcd; } return rr; } int main() { int i,j; scanf("%d%d",&n,&p); for(i=0;i<n;i++) { for(j=0;j<p;j++) { scanf("%d",&a[j][i]); a[j][i]--; } } for(i=0;i<n;i++) {b[0][i]=a[0][i];} for(i=1;i<p;i++)//求出TStep 即T1*t2*···*Tp; { for(j=0;j<n;j++) b[i][j]=a[i][b[i-1][j]]; } for(i=0;i<p;i++) { for(j=0;j<n;j++) c[i][b[i][j]]=j; } int ans=100000000; for(i=0;i<p;i++)//枚举y mod p=k; { bool flag=true; for(j=0;j<n;j++) { flag=find(b[p-1],c[i][j],j,d1[j],d2[j]); if(!flag)break; } if(!flag)continue; int tt=solve(d1,d2,n); if(tt!=-1&&tt*p+i+1<ans) ans=tt*p+i+1; } if(ans!=100000000)printf("%d\n",ans); else printf("No one knows.\n"); }