[交互]翻牌游戏

题意 ：你需要写两个程序 A,B。

首先交互库给出一个排列 P_{1\sim n} ，A 程序可以查看整个排列，并做至多一次交换。

然后，交互库给出一个值 k ，B 程序不知道排列，但可以每次询问排列的某个位置，需要在 \lceil n/2\rceil 次询问内找出 P_i=k 。

A,B 之间不得交流。

n\leq 2\times10^5

首先考虑 B 程序的输入集合。显然，当输入集合为全体排列时，B 程序无法保证每次都完成任务，这才需要 A 程序的协助，把一些“不好”的排列转化为“好”的排列，即简化 B 程序的输入集合。

观察一些简单的策略，我们发现，仅针对“值”或“位置”之一的交换策略都是双射，无法简化输入集合。这提示我们要总和考虑“值”与“位置”。

一个排列，将“值”与“位置”结合，我们可以想到置换。

由置换又可以想到环，于是我们让 B 程序遍历 k 所在的环（先询问 P_k=k_2 ，然后询问 P_{k_2} ，不断重复直到完成任务），这样最坏情况下所需操作次数是 最大环的大小。

A 只需要负责把最大环拆成两个较小的环即可，不难发现这样拆之后最大环的大小 \leq \lceil n/2\rceil 。

[构造]模与匹配

题意 ： 有一个左右各有 n 个点的二分图，点编号为 1\sim n 。

边 (i,j) 的权值为 i\bmod j。

给出 k ，要求选出一组匹配，使得权值恰为 k ，或指出无解。

n\leq 2\times10^5

首先考虑 k 的范围。

注意到 \mod i 的结果必 \leq i-1 ，一个显然的上界是 \dfrac{n(n-1)}{2} 。只需让 i 匹配 i+1 （特殊地，n 匹配 1）即可取到。

让 i 匹配 i ， 0 也可以取到，这是下界。

我们有 n! 种匹配方法而只用对付 O(n^2) 个值，先猜想解是稠密的，即 k=0\sim n(n-2)/2 都有解。

考虑选出一个集合（不含 n）使得和为 n ，然后进行适当操作使得这个集合恰有贡献。

不难想到，对这个集合进行轮换，这样除了最大的元素外，其余元素都获得了一个比自己大的模数。

为了让最大的元素也有贡献，将 n 加入集合来垫背。但是 n 换到 S 最左侧元素 c 时可能产生额外贡献。

再将 1 加入集合，这样 n 模的是 1 ，就没有贡献了。

剩下的任务就是选一个含 1 但不含 n 的集合使得和为 k 。

从大到小贪心，能选择选（保持余量 \geq 1 因为最后要选 1）即可。