Code Level: ※
Thinking Level: ※※

Description

YJC最近看了《模仿游戏》。他对里面图灵破解ENIGMA的过程产生了兴趣，决定自己模拟一下这个过程。
现在YJC正在破解一个2个转子的弱化版ENIGMA（没有反射器和连接板），他已经得到了明文和密文，他希望你能帮他破解出转子的布线方式。
不知道ENIGMA的题目解释：初始时有两个大小为m的数组a和b，分别是0∼m−1的一个排列。进行n次操作，每一次操作在0∼m−1之间选一个数x，求出结果y=b[a[x]]，把x和y写下来。之后，a数组向前循环移动一次，即(a[0],a[1],…,a[m−2],a[m−1])变成(a[1],a[2],…,a[m−1],a[0]).当a数组变回初始状态时，b数组向前循环移动一次。现在已知所有的x和y，求一组符合条件的a和b的初值。

$m^2<=n<=100000 （n表示操作次数）$

保证数据随机且一定有解

Solution

为了方便，我们可以表示y为

$y=b[a[(x+i)\ mod\ m]+i%m]$

而此时对a，b序列并未构成约束
考虑存在第二个相等的y值时

$y=b[a[(x+j)\ mod\ m]+\ mod\ m]$

则可以和上式构成

$a[(x_i+i)\ mod\ m]+i\ mod\ m=a[(x_j+j)\ mod\ m]+j\ mod\ m$

即

$a[(x_i+i)\ mod\ m]-a[(x_j+j)\ mod\ m]=j\ mod\ m-i\ mod\ m$

用并查集来维护差值从而维护约束条件即可
因为操作次数大于等于序列长度的平方，且保证数据唯一，可知a数组是可求的（序列每个值都被约束了）

Code

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int Nn=100005;
int N,M,F[Nn],X[Nn],Y[Nn],Prx[Nn],Pry[Nn],A[Nn],B[Nn];
int Find(int x){
    if(x==F[x]) return x;
    int t=Find(F[x]);
    A[x]=(A[x]+A[F[x]])%M;
    return F[x]=t;
}
int main(){
    scanf("%d%d",&N,&M); for(int i=0;i<N;i++) scanf("%d",&X[i]),X[i]=(X[i]+i)%M; for(int i=0;i<N;i++) scanf("%d",&Y[i]); //printf("%d<\n",N);
    for(int i=0;i<M;i++) F[i]=i; for(int i=0;i<N;i++)Prx[i]=-1;
    for(int i=0;i<N;i++)
    if(Prx[Y[i]]!=-1){
        int xx=Find(Prx[Y[i]]),yy=Find(X[i]); if(xx==yy) continue ;
        F[xx]=yy; A[xx]=(2*M-A[Prx[Y[i]]]+A[X[i]]+i/M%M-Pry[Y[i]])%M;
    }
    else Prx[Y[i]]=X[i],Pry[Y[i]]=i/M%M;
    for(int i=0;i<M;i++) Find(i);
    for(int i=0;i<N;i++) B[(A[X[i]]+i/M)%M]=Y[i];
    for(int i=0;i<M;i++) printf("%d ",A[i]); printf("\n");
    for(int i=0;i<M;i++) printf("%d ",B[i]);
    return 0;
}