置换问题
拉丁方
一个$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$次），可以用样的方式解决。
题目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$正则图，而我们知道这样的二分图是一定有完美匹配的（应用霍尔定理），因此我们可以不断消费掉新的数值，直到所有数被用完。
提供一道题目。
题目5：给定$2n$个长度为$n$的置换，且前$n$个置换构成拉丁方。且第$i$个数组和第$i+n$个数组至少有一列是相同的。现在打乱这$2n$个数组，要求从中找出$n$个置换构成一个拉丁方，如果有多个解，则任意输出一组。其中$1\leq n\leq 500$。
如果两个置换有公共列，那么就在它们二者之间加上一条边。现在的问题是找到一个大小为$n$的独立集，并且可以证明这一定是最大独立集。
我们可以先找到一个大小为$n$的最大匹配（考虑如果$i$和$i+n$匹配）。可以发现如果$i$和$j$匹配，意味着$i$和$j$要正好选择一个。这实际上是一个$n$个变量的2-sat问题，我们可以直接解决这个。总的时间复杂度为$O(n^3)$。
题目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$是否被选，可以确定连通块中其余所有顶点是否被选。
因此答案为$2^c$，$c$是剩下的连通块数目。
这个算法的时间复杂度为$O(n^3)$。
置换
一个$1$到$n$的置换是一个长度为$n$的序列$p_1,\ldots,p_n$，其中$1,2,\ldots,n$都正好出现一次。
置换可以看成是一个函数，对应的置换的乘法可以看做两个函数的复合，很显然两个置换的乘法结果还是一个有效的置换。
考虑$n$个顶点，并且对于任意$1\leq i\leq n$，加入一条有向边$(i,p_i)$。可以发现这时候图中存在若干个简单环，每个顶点都正好处于一个简单环中。
现在考虑$p^k(i)$，很显然我们只需要找到$i$所在的环，从$i$开始向前移动$k$次即可。因此我们得到了$O(n)$计算$p^k$的方式。
题目1：给定一个序列$a_0,\ldots,a_{n-1}$和整数$k$和$d$，接下来执行$n$次下面操作：
- 构建一个新序列$b$，初始为空
- 遍历所有数$a_i$，如果$i$能整除$k$，则将$i$移动到$b$的头部，否则移动到$b$的尾部。
- 将整个$b$序列向右旋转$d$步，即$b_i$放到$b_{i+d\pmod n}$
- 用$b$替换$a$
要求输出最终的序列$a$。其中$1\leq k\leq n\leq 10^6$。
可以发现第二步操作的实际上对应一个固定的置换$K$，同时第三步操作对应一个固定的置换$D$，而我们实际上要求$(D\cdot K)^n(a)$。
用上面提到的分环的方式，就可以$O(n)$时间复杂度求出$(D\cdot K)^n$了。
W形置换
定义$\mathrm{sgn}(x)$表示$x$的符号。我们称一个置换$p$是W形的当且仅当$\mathrm{sgn}(p_i-p_{i+1})=-\mathrm{sgn}(p_{i+1}-p_{i+2})$。
可以发现一个置换可以建立唯一的笛卡尔树，而一个笛卡尔树也可以唯一还原一个置换。因此我们可以认为笛卡尔树与置换之间一一对应。
接下来我们考虑W形置换对应的笛卡尔树具有的特性，不难发现：
- 一个结点如果有左孩子，则必定同时有右孩子（除非是最后一个元素）
- 一个结点如果有右孩子，则必定同时有左孩子（除非是第一个元素）
我们可以用笛卡尔树统计总共有多少个长度为$n$的W形置换，以$s$起始，以$t$终止。具体的思路就是令$dp(i,j)$表示仅考虑$1,2,\ldots,i$，总共形成$j$个森林的方案。可以发现转移只有$O(1)$种可能，因此我们得到了一个$O(n^2)$的算法。
下面我们考虑不限制起始和终止的W形置换数目。我们可以令$dp(i,j,k,t)$，表示仅考虑$1,2,\ldots,i$，总共形成$j$个森林的方案，其中$k$指示最左结点是否被选择，$t$表示最右结点是否被选择，这样我们得到了一个$O(n^2)$的算法。
提供一些题目：