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

作者: wjyyy 分类: 哈希,构造,解题报告 发布时间: 2018-10-29 19:54

点击量:30

 

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

 

问题描述

\(\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;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */