置换问题

Published: by Creative Commons Licence

  • Tags:

拉丁方

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

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

题目1：给定一个n×n的拉丁方A。接下来要处理q个请求，请求分5类：

  • 拉丁方循环下移k行（最后一行下移一行变成第一行）
  • 拉丁方循环右移k列（最后一列右移一列变成第一列）
  • 拉丁方每一行都单独取逆（置换P的逆Q也是一个置换，且满足QPi=i）
  • 拉丁方每一列都单独取逆
  • 拉丁方进行转置（B是A的转置，当且仅当Bj,i=Ai,j）
  • 给定i,j，查询Ai,j

其中1≤n≤103，1≤q≤106。要求最后输出经过变换的整个拉丁方。

提供一道题目。

这里我们认为置换从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(n2+q)。

题目2：有n×m的一个矩阵，每个单元都有一个数值，对于1≤i≤n，都有m个单元格的数值正好为i。现在要求重新整理每一行的数值（即对每一行进行重新排列），要求整理完后，每一列的元素两两不同。1≤n,m≤100

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

提供一道Kattis题目，再提供一道Atcoder题目。

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

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

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

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

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

提供一道题目。

题目5：给定2n个长度为n的置换，且前n个置换构成拉丁方。且第i个数组和第i+n个数组至少有一列是相同的。现在打乱这2n个数组，要求从中找出n个置换构成一个拉丁方，如果有多个解，则任意输出一组。其中1≤n≤500。

如果两个置换有公共列，那么就在它们二者之间加上一条边。现在的问题是找到一个大小为n的独立集，并且可以证明这一定是最大独立集。

我们可以先找到一个大小为n的最大匹配（考虑如果i和i+n匹配）。可以发现如果i和j匹配，意味着i和j要正好选择一个。这实际上是一个n个变量的2-sat问题，我们可以直接解决这个。总的时间复杂度为O(n3)。

题目6：给定2n个长度为n的置换，且前n个置换构成拉丁方。且第i个数组和第i+n个数组至少有一列是相同的。现在打乱这2n个数组，要求计算有多少大小为n的子集，形成拉丁方，结果对素数取模。

提供一道题目。

这个问题有一个构造性解法。首先如果存在一个置换，它的第j列是唯一的（仅考虑j列），那么这个置换一定是拉丁方的一部分。我们选择它，并删除所有与它冲突的置换。

重复这个过程，直到不能进行。这时候有两种可能，一种是拉丁方已经得到了，这时候算法正常结束，答案为1。否则所有列都不唯一。假设我们已选了k行，那么剩下的候选置换最多有2(n−k)个。考虑任意一列，它还有n−k个数未选，且这n−k个数都至少出现2次，因此可以保证每个数都正好出现两次。

这意味着候选置换中正好n−k个的属于前n行，n−k个属于后n行，且后者相互不冲突。如果把冲突关系建立成边，形成的图是二分图。且如果a和b冲突，意味着a和b中正好一个被选。因此对于同一个连通块，考虑其中任意一个顶点u是否被选，可以确定连通块中其余所有顶点是否被选。

因此答案为2c，c是剩下的连通块数目。

这个算法的时间复杂度为O(n3)。

置换

一个1到n的置换是一个长度为n的序列p1,…,pn，其中1,2,…,n都正好出现一次。

置换可以看成是一个函数，对应的置换的乘法可以看做两个函数的复合，很显然两个置换的乘法结果还是一个有效的置换。

考虑n个顶点，并且对于任意1≤i≤n，加入一条有向边(i,pi)。可以发现这时候图中存在若干个简单环，每个顶点都正好处于一个简单环中。

现在考虑pk(i)，很显然我们只需要找到i所在的环，从i开始向前移动k次即可。因此我们得到了O(n)计算pk的方式。

题目1：给定一个序列a0,…,an−1和整数k和d，接下来执行n次下面操作：

  1. 构建一个新序列b，初始为空
  2. 遍历所有数ai，如果i能整除k，则将i移动到b的头部，否则移动到b的尾部。
  3. 将整个b序列向右旋转d步，即bi放到bi+d(modn)
  4. 用b替换a

要求输出最终的序列a。其中1≤k≤n≤106。

可以发现第二步操作的实际上对应一个固定的置换K，同时第三步操作对应一个固定的置换D，而我们实际上要求(D⋅K)n(a)。

用上面提到的分环的方式，就可以O(n)时间复杂度求出(D⋅K)n了。

W形置换

定义sgn(x)表示x的符号。我们称一个置换p是W形的当且仅当sgn(pi−pi+1)=−sgn(pi+1−pi+2)。

可以发现一个置换可以建立唯一的笛卡尔树，而一个笛卡尔树也可以唯一还原一个置换。因此我们可以认为笛卡尔树与置换之间一一对应。

接下来我们考虑W形置换对应的笛卡尔树具有的特性，不难发现：

  • 一个结点如果有左孩子，则必定同时有右孩子（除非是最后一个元素）
  • 一个结点如果有右孩子，则必定同时有左孩子（除非是第一个元素）

我们可以用笛卡尔树统计总共有多少个长度为n的W形置换，以s起始，以t终止。具体的思路就是令dp(i,j)表示仅考虑1,2,…,i，总共形成j个森林的方案。可以发现转移只有O(1)种可能，因此我们得到了一个O(n2)的算法。

下面我们考虑不限制起始和终止的W形置换数目。我们可以令dp(i,j,k,t)，表示仅考虑1,2,…,i，总共形成j个森林的方案，其中k指示最左结点是否被选择，t表示最右结点是否被选择，这样我们得到了一个O(n2)的算法。

提供一些题目：