P5235

Last_kiss_Snow_Dog6 · 2023-08-23 10:52:34 · 题解

题目传送门

Tags

置换与置换群，Schreier-Sims 算法没有群的相关知识的同学就可以拿 40 分裸暴力然后继续切其他题啦。

Solution

被一道板子题坑了两天

根据题目，图上每个点都有两个信息需要维护：点的编号和棋子编号。由于在一个确定的局面下二者之间有一一对应关系，很自然的想法便是把其中一个作为下标，另一个作为值。又由于题目给出的条件几乎都和点编号有关，显然把棋子编号作为下标更加靠谱。于是我们维护的是一个 n 阶排列 P ，其中 P_i 表示编号为 i 的棋子所在点的编号，那么每一次操作就是把这个排列的首项 P_0 与某一项交换。下面来考虑点的编号在转移过程中满足的若干性质。不难发现这样一件事： V_1V_2 ⋯ V_t ，并且 0 号棋子在这个环中的某一点（不妨设为 V_1 ）上的话，经过 t 次操作使得 0 棋子围着环转一圈之后，原先在 V_2,V_3,⋯,V_t 上的棋子就会到 V_t,V_2,⋯,V_{t-1} 上。将这一过程重复若干次便可取遍所有的圆上排列，而这一过程的本质就是置换。

显然，对于每一个简单环，我们都可以得到一个这样的置换。记这些置换组成的集合为 R 。不过这样得到的置换有一个问题，那就是我们并没有讨论 0 所在的点的变化。于是我们可以想办法让这一因素从我们的讨论范围中消失——对于每种局面，先把 0 沿一条路径移动到某一个确定的点（不妨设为 1 号点）上，即钦定 P_0=1 ，于是只需讨论排列 P_1,P_2,⋯,P_{t-1} 之间的转移。可以证明这样做是正确的。设任意一种局面 S 经此处理之后得到的排列为 f(S) ，于是问题就转化为对于给定的初始状态 A 和每次给出的状态 B ， f(B) 能否由 f(A) 经若干 R 中的置换作用之后得到。如果把排列也看作是置换的话，那就是在问 f(B)⋅f(A)-1 是否在以 R 为生成集的置换群中。至此，问题已经被解决的一大半，剩下的就是如何快速判断一个给定的置换是否在以给定集合为生成集的群中。

#include<bits/stdc++.h>
using namespace std;
const int MX=55;
#define pb push_back

int N,M,Q,pre[MX],f[MX],g[MX],pos[MX],t,ls[MX],idx,m,b[MX];
int lr[MX],rid[MX][MX];
vector<int> G[MX];
struct Permutation
{
    int a[MX];
    Permutation(){memset(a,0,sizeof(a));}
    bool isI()
    {
        for(int i=1;i<N;i++)if(a[i]!=i)return 0;
        return 1;
    }
    Permutation operator * (Permutation& b)
    {
        static Permutation ans;
        for(int i=1;i<N;i++)ans.a[i]=b.a[a[i]];
        return ans;
    }
    Permutation inverse()
    {
        static Permutation ans;
        for(int i=1;i<N;i++)ans.a[a[i]]=i;
        return ans;
    }
}s[MX][MX],r[MX][MX],rr[MX][MX],ans;
bool vis[MX],ins[MX];

inline int read()
{
    static int x;
    static char c;
    c=getchar(),x=0;
    while(!isdigit(c))c=getchar();
    while(isdigit(c))x=x*10+c-'0',c=getchar();
    return x;
}
inline void dfs(int u,int f)
{
    int w;
    pre[u]=f,vis[u]=1,ins[u]=1;
    for(auto i:G[u])if(i!=f)
    {
        if(vis[i])
        {
            if(!ins[i])continue;
            ++t;
            for(int j=0;j<N;j++)s[1][t].a[j]=j;
            w=u;
            while(pre[w]!=i)s[1][t].a[w]=pre[w],w=pre[w];
            s[1][t].a[w]=u;
        }
        else dfs(i,u);
    }
    ins[u]=0;
}
inline void bfs()
{
    int u=b[idx],v;
    static int q[MX],hd,tl;
    static char vst[MX];
    static Permutation t;
    q[hd=tl=1]=u;
    memset(vst+1,0,sizeof(char)*(N-1));
    vst[u]=1;
    for(int i=1;i<N;i++)r[idx][i].a[1]=0;
    for(int i=1;i<N;i++)r[idx][u].a[i]=rr[idx][u].a[i]=i;
    lr[idx]=1,rid[idx][1]=u;
    while(hd<=tl)
    {
        u=q[hd++];
        for(int i=1;i<=ls[idx];i++)
        {
            t=r[idx][u]*s[idx][i],v=t.a[b[idx]];
            if(!vst[v])
            {
                vst[v]=1,q[++tl]=v;
                r[idx][v]=t,rr[idx][v]=t.inverse();
                rid[idx][++lr[idx]]=v;
            }
        }
    }
}
inline void Divide(Permutation& h)
{
    for(int i=idx+1;i<=m;i++)if(h.a[b[i]]!=b[i])
    {
        if(!r[i][h.a[b[i]]].a[1])return;
        h=h*rr[i][h.a[b[i]]];
    }
}
inline void Schreier_Sims()
{
    Permutation h;
    bool o;
    idx=m=1;
    for(int i=1;i<=ls[1];i++)for(int j=1;j<N;j++)
        if(s[1][i].a[j]!=j)b[1]=j;
    bfs();
    while(idx)
    {
        o=1;
        for(int i=1;o&&i<=lr[idx];i++)for(int j=1;j<=ls[idx];j++)
        {
            h=r[idx][rid[idx][i]]*s[idx][j];
            h=h*rr[idx][h.a[b[idx]]];
            Divide(h);
            if(!h.isI()){o=0;break;}
        }
        if(o)--idx;
        else
        {
            if(++idx>m)
            {
                ls[++m]=0;
                for(int j=1;j<N;j++)if(h.a[j]!=j)b[m]=j;
            }
            s[idx][++ls[idx]]=h;
            bfs();
        }
    }
}
inline void Transfer(int *A)
{
    int u=-1;
    for(int i=0;i<N;i++)if(!A[i])u=i;
    while(u)swap(A[u],A[pre[u]]),u=pre[u];
    for(int i=0;i<N;i++)pos[A[i]]=i;
    memcpy(A,pos,sizeof(int)*N);
}

int main()
{
    N=read(),M=read(),Q=read();
    for(int i=1,u,v;i<=M;i++)
        u=read()-1,v=read()-1,G[u].pb(v),G[v].pb(u);
    dfs(0,-1);
    if(ls[1]=t)Schreier_Sims();
    for(int i=0;i<N;i++)f[i]=read();
    Transfer(f);
    while(Q--)
    {
        for(int i=0;i<N;i++)g[i]=read();
        Transfer(g);
        for(int i=1;i<N;i++)ans.a[f[i]]=g[i];
        if(t)Divide(ans);
        puts(ans.isI()?"Yes":"No");
    }
    return 0;
}