锐客网

  1. 首页 > it技术 > >

数学|[UOJ 287][WC 2017] 棋盘

数学wcUOJ群论

Description

给你一张n个点m条边的无向图，点编号1,2,?,n ，每个点上放有一枚棋子，棋子编号0,1,?,n?1 ，一次操作是指将编号为0的棋子与图上和它所在点有边相连的点上的棋子交换位置。现在有q组询问，每次询问给定的局面是否能从给出的初始局面经若干次操作得到。
n≤50,m≤100,q≤1000
时间限制：3s，空间限制：1G
题目传送门
Tags
置换与置换群，Schreier-Sims算法
没有群的相关知识的同学就可以拿40分裸暴力然后继续切其他题啦
Solution
被一道板子题坑了两天。。。
根据题目，图上每个点都有两个信息需要维护：点的编号和棋子编号。由于在一个确定的局面下二者之间有一一对应关系，很自然的想法便是把其中一个作为下标，另一个作为值。又由于题目给出的条件几乎都和点编号有关，显然把棋子编号作为下标更加靠谱。
于是我们维护的是一个n阶排列P ，其中Pi表示编号为i的棋子所在点的编号，那么每一次操作就是把这个排列的首项P0与某一项交换。
下面来考虑点的编号在转移过程中满足的若干性质。
不难发现这样一件事：如果原图G存在一个环V1V2?Vt ，并且0号棋子在这个环中的某一点（不妨设为V1 ）上的话，经过t次操作使得0棋子围着环转一圈之后，原先在V2,V3,?,Vt上的棋子就会到Vt,V2,?,Vt?1上。将这一过程重复若干次便可取遍所有的圆上排列。
而这一过程的本质就是置换

(V2VtV3V2V4V3??VtVt?1)
显然，对于每一个简单环，我们都可以得到一个这样的置换。记这些置换组成的集合为 R。
不过这样得到的置换有一个问题，那就是我们并没有讨论 0所在的点的变化。于是我们可以想办法让这一因素从我们的讨论范围中消失——对于每种局面，先把 0沿一条路径移动到某一个确定的点（不妨设为 1号点）上，即钦定 P0=1，于是只需讨论排列 P1,P2,?,Pn?1之间的转移。可以证明这样做是正确的。
设任意一种局面 S经此处理之后得到的排列为 f(S)，于是问题就转化为对于给定的初始状态 A和每次给出的状态 B， f(B)能否由 f(A)经若干 R中的置换作用之后得到。
如果把排列也看作是置换的话，那就是在问 f(B)?f(A)?1是否在以 R为生成集的置换群中。
至此，问题已经被解决的一大半，剩下的就是如何快速判断一个给定的置换是否在以给定集合为生成集的群中。
为了解决这个问题，我们要引入Schreier-Sims算法。
太长不看版 自行查阅2014年国家集训队论文《对置换群有关算法的初步研究》，剩下的部分是论文中介绍的算法的应(mú)用(bǎn)。
正常版 坑坑坑
AC Code
【数学|[UOJ 287][WC 2017] 棋盘】时间复杂度： O(n5) （大概吧）
空间复杂度： O(n3)
#include using namespace std; const int MX=55; #define pb push_backint 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 G[MX]; struct Permutation { int a[MX]; Permutation(){memset(a,0,sizeof(a)); } bool isI() { for(int i=1; im) { ls[++m]=0; for(int j=1; j

    推荐阅读


    上一篇：属性动画|属性动画 翻牌效果

    下一篇：数学-数论|【51Nod1227】平均最小公倍数-杜教筛