置换问题

Published: by Creative Commons Licence

  • Tags:

拉丁方

一个$n\times n$的矩阵是拉丁方,当且仅当矩阵的每个元素都是$1$到$n$之间的整数,且每一行每一列都是一个置换。

这里我们把第$i$行第$j$列的元素$A_{i,j}$视作一个向量$(i,j,A_{i,j})$,而总共$n^2$个向量互不相同,组成一个集合$S$,这里的集合称作拉丁方集合,可以发现固定任意一个维度的值,另外两个维度的值都分别是$1$到$n$的一个置换,而当固定两个维度的时候,第三个维度的值也随之确定。拉丁方集合和拉丁方一一对应。

题目1:给定一个$n\times n$的拉丁方$A$。接下来要处理$q$个请求,请求分5类:

  • 拉丁方循环下移$k$行(最后一行下移一行变成第一行)
  • 拉丁方循环右移$k$列(最后一列右移一列变成第一列)
  • 拉丁方每一行都单独取逆(置换$P$的逆$Q$也是一个置换,且满足$Q_{P_i}=i$)
  • 拉丁方每一列都单独取逆
  • 拉丁方进行转置($B$是$A$的转置,当且仅当$B_{j,i}=A_{i,j}$)
  • 给定$i,j$,查询$A_{i,j}$

其中$1\leq n\leq 10^3$,$1\leq q\leq 10^6$。要求最后输出经过变换的整个拉丁方。

提供一道题目

这里我们认为置换从$0$开始,因此下述的所有操作都是在模$n$的含义下进行的。

之后我们考虑下移$k$步,考虑创建一个新集合$S'$,对于$S$中的元素$(i,j,v)$,我们将向$S'$中加入一个新的元素$(i+k,j,v)$。同理对于右移$k$步操作,我们则向$S'$中加入一个新的元素$(i,j+k,v)$。可以发现得到的新集合依旧是一个拉丁方集合。

再考虑行逆操作,我们创建一个新集合$S'$,对于$S$中的元素$(i,j,v)$,我们将向$S'$中加入一个新的元素$(i,v,j)$。而对于列逆操作,我们则向$S'$中加入一个新的元素$(v,j,i)$。而对于转置操作,实际上是向$S'$中加入一个新的元素$(j,i,v)$,可以发现得到的新集合依旧是一个拉丁方集合。

我们可以维护一个长度为$3$的向量,之后每个修改操作实际上都对应向量加法和维度交换。对于查询操作,我们发现给定了$(i,j)$,我们需要查出具体是哪两个维度作用,再根据这两个维度去查第三个维度,我们可以预先处理来加速查询操作,总共有$3$种可能性。

因此时间复杂度为$O(n^2+q)$。

题目2:有$n\times m$的一个矩阵,每个单元都有一个数值,对于$1\leq i\leq n$,都有$m$个单元格的数值正好为$i$。现在要求重新整理每一行的数值(即对每一行进行重新排列),要求整理完后,每一列的元素两两不同。$1\leq n,m\leq 100$

霍尔定理的经典用途。首先我们先考虑第一列上的元素。我们建立一个二分图,每一行都对应左边一个顶点,而每个数值都对应右边的一个顶点。如果第$i$行有数值$j$存在,那么就在$L_i$和$R_j$之间加一条边。现在我们通过霍尔定理证明一定存在完美匹配,考虑$k$行组成的集合,我们可以利用鸽巢原理,可以直接断言,这些行中不同元素的数目至少有$k$个,否则的话至少一个元素出现次数超过$m$,这是不可能的。因此我们可以找到任意一个完美匹配。之后我们考虑后面$m-1$列的情况,我们发现这是原问题的一个子问题(每个元素恰好出现$m-1$次),可以用样的方式解决。

提供一道Kattis题目,再提供一道Atcoder题目

题目3:有$n\times n$的一个矩阵,每一行每一列都对应一个$1$到$n$的置换,这样的矩阵称为拉丁方。现在矩阵中前$k$行已经被填入数值了,要求你将其余数值填入其余单元格中。如果存在解,输出任意一组,否则报告无解。其中$1\leq n\leq 100$

首先很显然每行每列元素都需要不同,否则无解。那么假如通过了检测,那么就可以通过题目2的方式解决剩下的部分。

题目4:有$n\times n$的一个矩阵,每一行每一列都对应一个$1$到$n$的置换,这样的矩阵称为拉丁方。现在矩阵中有$k$个不同的数值已经填入矩阵的$nk$个单元中了,要求你将其余数值填入其余单元格中。如果存在解,输出任意一组,否则报告无解。其中$1\leq n\leq 100$

首先为了保证拉丁方有解,我们需要先保证每行每列都没有重复元素。

之后我们按数值进行填充,任意取一个未填充过的数值,填入其中的$n$个单元格中。由于每行每列需要恰好填入一个元素,我们可以建立这样的二分图,每一行对应左边某个顶点,每一列对应右边一个顶点,如果$(i,j)$为空,就在$X_i$和$X_j$之间连边。假设现在我们处理了$t$个数了,那么我们会发现每一行每一列都还有$n-t$个单元格可用,即对应二分图中每个顶点的度数都是$n-t$,这意味着二分图是一个$n-t$正则图,而我们知道这样的二分图是一定有完美匹配的(应用霍尔定理),因此我们可以不断消费掉新的数值,直到所有数被用完。

提供一道题目