密码游戏 题解【构造】【哈希】

点击量：192

    转化比较多的一道题，还需要一定构造技巧。

目录

问题描述

\(\text{YJC}\)很喜欢玩游戏， 今天他决定和朋友们玩密码游戏。

密码游戏的规则是这样的：初始时有两个大小为\(m\)的数组\(a\)和\(b\)，分别是\(0\sim m-1\)的一个排列。每一次操作在\(0\sim 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\)，如果\(\text{YJC}\)能求出任意一组符合条件的\(a\)和\(b\)的初值，\(\text{YJC}\)就赢了。

\(\text{YJC}\)很想赢得游戏，但他太笨了，他想让你帮他算出\(a\)和\(b\)的初值。

输入格式

第一行包含两个整数\(n\)和\(m\)，表示操作了多少次和\(a,b\)数组的大小。

第二行包含\(n\)个整数，第\(i\)个数表示第\(i\)次选出的\(x\)。

第二行包含\(n\)个整数，第\(i\)个数表示第\(i\)次求出的\(y\)。

输出格式

第一行包含\(m\)个整数，表示\(a\)的初值。

第二行包含\(m\)个整数，表示\(b\)的初值。如果有多组答案，输出任意一组即可。

输入输出样例

输入样例：

4 2
0 0 0 0
0 1 1 0

输出样例：

0 1
0 1

数据范围与约定

对于\(30\%\)的数据，满足\(m\le 5,n\le 1000\)。

对于\(100\%\)的数据，满足\(2\le m\le 26,m^2\le n\le 100000\)， 保证数据随机， 且存在至少一组\(a\)和\(b\)。

题解：

    这道题需要把数组的循环变化用数值表示出来，然后构造答案，找到信息之间的关系。同时因为数据是完全随机的，所以信息之间的关系是可以期望的。即使\(a,b\)数组都在滚动，它们每一位被选中的概率也都是一样的，每个位置期望被选中的次数是\(\frac nm\)。

    每次\(a\)数组会整体左移一位，因此\(b[a[x]]\)中的\(x\)在第\(i\)次（最开始算作第\(0\)次）时需要加上\(i\)，同时对\(m\)取模。每过\(m\)次\(b\)数组会整体左移一位，所以在第\(i\)次需要对\(a[x]\)加上\(\left\lfloor\frac im\right\rfloor\)。最终就是\(b[a[(x_i+i)\bmod m]+\left\lfloor\frac im\right\rfloor]=y_i\)。

    如果设每个位置表示\(b[a[x_i+p]+q]=y_i\)，并且\(a,b\)数组都是排列，那么由于\(b[]\)对于\(y_i\)是双射，\(a[x_i+p]+q\)对于\(y_i\)就也是双射，我们对于相同的\(y\)维护\(\{a[x+p]+q\}\)集合，每个\(y\)就像一个哈希值，则有

\[\left\{\begin{matrix}
a[(x_{p_1}+p_1)\bmod m]+q_1=y\\
a[(x_{p_2}+p_2)\bmod m]+q_2=y\\
\vdots \\
a[(x_{p_2}+p_k)\bmod m]+q_k=y
\end{matrix}\right.\]

    我们拿任意两个式子相减，就可以得到两个式子之间的关系形如\(a[(x_{p_1}+p_1)\bmod m]-a[(x_{p_2}+p_2)\bmod m]=q_1-q_2\)，那么这两点的关系就是差值为\(q_1-q_2\)。我们对于每个固定的\(y\)，都找到这样的关系，然后进行\(\tt BFS\)，类似在图中，我们把两点之间的关系用邻接矩阵存起来，根据每两个点之间的关系可以把所有\(i\)的\(a[i]\)都求出来。如果遇到图不连通的情况，我们只需要多枚举几个\(y\)的值，在各个集合中找到一个连通图，构造出\(b\)，把答案输出即可。

    \(b\)可以直接通过输入数据的\(b[a[x_i]]=y_i\)来构造，期望时间复杂度为\(O(\frac{n^2}{m^2})\)。

Code：

#include<cstdio>
#include<cstring>
struct rela
{
    int u,v;//编号和差值
    int nxt;
    rela(int u,int v,int nxt)
    {
        this->u=u;
        this->v=v;
        this->nxt=nxt;
    }
    rela(){}
}r[100001];
int head[30],rcnt=-1;
void add(int u,int v,int p)
{
    r[++rcnt]=rela(u,v,head[p]);
    head[p]=rcnt;
}
int a[100100],b[100100],x[100100],y[100100];
int f[30][30],m;
bool used[30];
void dfs(int x)
{
    for(int i=0;i<m;++i)
        if(!used[i]&&f[x][i]!=0x3f3f3f3f)
        {
            a[i]=a[x]+f[x][i];
            used[i]=1;
            dfs(i);
        }
}
int main()
{
    memset(head,-1,sizeof(head));
    int n;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;++i)
        scanf("%d",&x[i]);
    for(int i=0;i<n;++i)
    {
        scanf("%d",&y[i]);
        add((x[i]+i)%m,i/m,y[i]);
    }
    int flag=1;
    for(int i=0;flag&&i<m;++i)
    {
        memset(f,0x3f,sizeof(f));
        for(int j=head[i];~j;j=r[j].nxt)
            for(int k=r[j].nxt;~k;k=r[k].nxt)
            {
                int tmp=r[j].v-r[k].v;
                f[r[j].u][r[k].u]=tmp;
                f[r[k].u][r[j].u]=-tmp;
            }
        memset(used,0,sizeof(used));
        a[0]=0;
        flag=0;
        used[0]=0;
        dfs(0);
        for(int j=0;j<m;++j)
            a[j]%=m;
        int mn=0;
        for(int j=0;j<m;++j)
        {
            if(!used[j])
                flag=1;
            mn=mn<a[j]?mn:a[j];
        }
        if(!flag)
            for(int j=0;j<m;++j)
                a[j]=(a[j]-mn)%m;
    }
    //此时求每个b
    for(int i=0;i<n;++i)
        b[(a[(x[i]+i)%m]+i/m)%m]=y[i];
    for(int i=0;i<m;++i)
        printf("%d ",a[i]);
    puts("");
    for(int i=0;i<m;++i)
        printf("%d ",b[i]);
    return 0;
}