首页 > 代码库 > PA 2012 求解判断置换A^k=B
PA 2012 求解判断置换A^k=B
题目大意：每组数据共有3行。
第一行有一个正整数n。
第二行有n个正整数A_1, A_2, ..., A_n表示置换A。
第三行有n个正整数B_1, B_2, ..., B_n表示排列B。判断能否达到B。n<=1000000
思考过程：这道题也是模拟赛中遇到的，刚开始，很显然的想出了置换群，并且发现了几种可以达到的充分且必要条件（这里我们将b数组重新定义为i最后处在的位置）
（1）a,b必在一个置换群中
（2）x≡bi(mod ai)其中x为置换次数，ai,bi为每一个置换群的大小，和需要变换的最小次数
到了这一步，就不知道怎么做了。。。。。。
看完标程后，终于知道了其中的奥秘
题解：将ai分解质因数，因为x mod ab=c可以推出x mod a=c mod a，所以，我们可以记录每一个质数的余数，再进行判断，首先要用线性筛求出每个数的最小质数（这样可以节约时间）然后再分解，具体看代码。
1 #include<iostream> 2 #include<cstring> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstdio> 6 using namespace std; 7 const int maxn=1000005; 8 int n; 9 int a[maxn]; 10 int f[maxn]; 11 int num[maxn]; 12 int all[maxn]; 13 int b[maxn]; 14 char tmp[20]; 15 int p[maxn]; 16 int col; 17 int t; 18 bool flag; 19 void read(int &x){ 20 char ch = getchar(); while (ch < ‘0‘ || ch > ‘9‘) ch = getchar(); 21 for (x = 0; ch >= ‘0‘ && ch <= ‘9‘; ch = getchar()) x = x*10+ch-48; 22 } 23 int gcd(int x,int y) 24 { 25 if(y==0)return x; 26 return gcd(y,x%y); 27 } 28 struct eq2{ int r, p, a; }e2[7100000]; 29 bool cmp(eq2 u,eq2 v) 30 { 31 if(u.p!=v.p)return u.p<v.p; 32 return u.a>v.a; 33 } 34 int l2; 35 int prm[11000000], lp; 36 int fac[11000000]; 37 void init(){ 38 for(int i=2;i<=1000000;i++){ 39 //cout<<i<<endl; 40 if (!fac[i]){ prm[++lp] = i; fac[i] = lp;} 41 for(int j=1;j<=lp;j++) 42 { 43 //cout<<"find"; 44 if (prm[j]*i > 1000000) break; 45 fac[prm[j]*i] = j; 46 if (fac[i] == j) break; 47 } 48 } 49 } 50 bool solve() 51 { 52 int l2=0; 53 for(int i=1;i<=col;i++) 54 { 55 int t=all[i]; 56 while(t!=1) 57 { 58 //cout<<t<<endl; 59 int ff=fac[t]; 60 //cout<<ff<<endl; 61 e2[++l2].p=ff; 62 e2[l2].a=1; 63 while(fac[t]==ff) 64 { 65 t/=prm[ff]; 66 e2[l2].a*=prm[ff]; 67 } 68 e2[l2].r=p[i]%e2[l2].a; 69 70 } 71 } 72 // cout<<l2<<endl; 73 sort(e2+1,e2+l2+1,cmp); 74 for(int i=1;i<l2;i++) 75 { 76 if(e2[i].p==e2[i+1].p) 77 { 78 if (e2[i].r%e2[i+1].a != e2[i+1].r){return false;} 79 } 80 } 81 return true; 82 } 83 int main() 84 { 85 // freopen("ever.in","r",stdin); 86 // freopen("ever.out","w",stdout); 87 init(); 88 // cout<<fac[4]<<endl; 89 while(scanf("%d",&n)!=EOF) 90 { 91 gets(tmp); 92 flag=true; 93 for(int i=1;i<=n;i++) 94 read(a[i]); 95 memset(f,0,sizeof(f)); 96 memset(p,0,sizeof(p)); 97 col=0; 98 for(int i=1;i<=n;i++) 99 {100 if(f[i])continue;101 f[i]=++col;102 t=1;103 num[i]=t;104 int j=a[i];105 while(!f[j])106 {107 t++;108 num[j]=t;109 f[j]=col;110 j=a[j];111 }112 all[col]=t;113 }114 for(int i=1;i<=n;i++)115 {116 int x;117 read(x);118 b[x]=i;119 }120 for(int i=1;i<=n;i++)121 {122 int x=b[i];123 //cout<<i<<" "<<x<<endl;124 if(f[i]!=f[x])125 {126 flag=false;127 128 }129 else130 {131 if(!p[f[i]])132 {133 p[f[i]]=(num[x]-num[i]+all[f[i]])%all[f[i]];134 }135 else 136 {137 if((num[x]-num[i]+all[f[i]])%all[f[i]]!=p[f[i]])138 {139 flag=false;140 }141 }142 }143 }144 // for(int i=1;i<=col;i++)cout<<p[i]<<" "<<all[i]<<endl;145 if(!flag){puts("Forever");continue;}146 if(solve())puts("Ever");else puts("Forever");147 }148 return 0;149 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。