首页 > 代码库 > hdu 3430 Shuffling(置换群+中国剩余定理)

hdu 3430 Shuffling(置换群+中国剩余定理)

2024-10-10 11:53:39   215人阅读

题目链接：hdu 3430 Shuffling

题意：

给出n张牌，标号为1-n，然后给出两个序列，序列1表示序列1,2,3,4……,n洗一次牌后到达的.

序列2表示目标序列，问初始序列按序列1的洗牌方式洗几次能到达序列2的情况，如果不能到达输出-1.

题解：

在初始序列和序列1的变换中找出1能变到那些牌，这些牌构成一个集合，这些集合中的牌必然是能够相互到达的。

然后在序列2中也找出这样一个集合，集合中这些元素的相互顺序是要一样的，这就是判断能否达到。

然后这样可以列出几个线性同余方程组，用中国剩余定理求解即可。

网上的题解写的比较详细：传送门

技术分享 
 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=a;i<=b;++i)
 3 using namespace std;
 4 typedef long long ll;
 5 
 6 const int N=1000;
 7 int n,a[N],b[N],vis[N],cnt,flag,c[N];
 8 ll x[N],y[N];
 9 
10 ll ex_gcd(ll a,ll b,ll &x,ll &y){
11     if(!b){ x=1,y=0; return a; }
12     ll ret=ex_gcd(b,a%b,y,x);
13     y-=a/b*x;
14     return ret;
15 }
16 
17 ll CRT(int n,ll a[],ll b[]){//x=a(mod b)
18     ll a1=a[1],b1=b[1],x,y,t,gcd;    
19     for(ll i=2;i<=n;i++){  
20         gcd=ex_gcd(a1,a[i],x,y);  
21         if((b[i]-b1)%gcd)return -1;//无解
22         t=a[i]/gcd;
23         x=(x*(b[i]-b1))/gcd,x=(x%t+t)%t; 
24         b1=a1*x+b1,a1=(a1*a[i])/gcd;
25         b1=(b1%a1+a1)%a1;  
26     }  
27     return b1;
28 }  
29 
30 int main()
31 {
32     while(~scanf("%d",&n),n)
33     {
34         F(i,1,n)scanf("%d",a+i);
35         F(i,1,n)scanf("%d",b+i);
36         memset(vis,0,sizeof(vis));
37         flag=cnt=0;
38         F(i,1,n)if(!vis[i])
39         {
40             int u=i,cnt1=0,pos=0;
41             while(!vis[u])vis[u]=1,c[cnt1++]=u,u=a[u];
42             while(pos<cnt1&&b[i]!=c[pos])pos++;
43             if(pos==cnt1){flag=1;goto en;}
44             x[++cnt]=cnt1,y[cnt]=pos;
45             for(u=a[i];u!=i;u=a[u])
46                 if(b[u]!=c[(++pos)%cnt1]){flag=1;goto en;}
47         }
48         en: printf("%lld\n",flag?-1:CRT(cnt,x,y));
49     }
50     return 0;
51 }
View Code

 

hdu 3430 Shuffling(置换群+中国剩余定理)


联系
我们