简要题意

有 $N$ 个人，$L$ 把锁和 $(L+K)$ 把钥匙。其中有 $L$ 把真钥匙，分别可以打开一把锁；另外 $K$ 把钥匙是假的，不能打开任何锁。

所有人按顺序尝试钥匙。每个人的策略都是最大化选择的钥匙打开选择的门的概率。如果有多种概率最大的组合，则等概率选择其中一种。

求打开所有锁之后每个人开锁次数的期望。

$1\le N\le 50$, $1\le L\le 5000$, $0\le K\le 50$

求解策略

为了解决这个问题，我们需要知道每个人具体会如何选择钥匙和锁。

显然，最开始的人不知道任何信息，所以只能随机选择一把钥匙和一把锁。

如果第一个人没有打开锁，第二个人有三种选法：选同一把钥匙开不同锁，选不同钥匙开同一把锁，选不同钥匙和锁。

选同一把钥匙开不同锁，或者选不同钥匙开同一把锁，解锁概率都是 $1/(L+K-1)$；选不同钥匙和锁的解锁概率是

$$\frac{1 - \frac{1}{L+K-1}}{L+K-1} = \frac{L+K-2}{(L+K-1)^2} < \frac{1}{L+K-1}$$

所以第二个人会以 $(L-1)/(2L+K-2)$ 的概率选同一把钥匙开不同锁，以 $(L+K-1)/(2L+K-2)$ 概率选不同钥匙开同一把锁。

结论

同理可以继续分析后续各人的策略。结论为：如果第二个人选择了同一把钥匙，则接下来每个人都会选择这把钥匙；如果第二个人选择了同一把锁，则接下来每个人都会选择这把锁。

不难想到记录 $f_i(l, k)$ 表示 $L=l, K=k$ 时第 $i$ 个人的期望开锁次数，则可以对 $f$ 进行 DP。

另一种做法是，记 $p_i(l, k)$ 表示已经打开了 $l$ 把锁，发现 $k$ 把假钥匙，轮到第 $i$ 个人进行首次尝试的概率（此时除了 $l$ 和 $k$ 以外没有任何额外信息，重置到所有组合等概率的状态），另外记 $E_i$ 表示答案。

出题人写的是后一种写法，验题人写的是前一种写法，都可以通过。

转移

因为决策有三类，所以转移分为三种：第一个人直接开锁，第二个人开锁（分相同钥匙还是相同锁讨论），后续其余人开锁（同样分类讨论）。

前两种转移都是 $O(1)$ 的，第三种转移如果直接做是 $O(L+K)$ 的，总复杂度 $O(NLK\cdot (L+K))$，不能通过本题。

推式子可知，对于第三种转移而言，恰是某一次尝试时解锁的概率是相等的。直观理解：多人抓阄，是每个人按顺序抓并直接打开，还是所有人先抓完再一起打开，并不影响每个人抽中的概率。

由此可知，我们只需要统计每个第三种转移中，每个人可以尝试多少次，再乘上相应的概率即可。这样可以将复杂度降低到 $O(NLK\cdot N)$，但仍然不能通过。

如果你常数足够小，有可能可以松过去

进一步优化

冷静分析：因为尝试是按顺序进行的，所以尝试的次数很平均。

• 如果尝试次数 $x$（如果是相同钥匙，就是剩余锁的数量；如果是相同锁，就是剩余钥匙的数量）恰好是 $N$ 的倍数，则每个人恰好试 $x/N$ 次。
• 否则，前 $x \mod N$ 个人可以试 $\lceil x/N \rceil$ 次，其余人可以试 $\lfloor x/N \rfloor$ 次。

因为相同尝试次数（也即相同转移系数）的极长连续段只有 $O(1)$ 个，所以可以用前缀和的方式，将第三种转移优化到 $O(1)$。总复杂度 $O(NLK)$，可以通过本题。

简要题意

给定包含 $N$ 个长度为 $M$ 的 01 串的集合 $S$，有 $Q$ 组询问，每个询问给出一个长度为 $M$ 的 01 串 $t_i$，求集合 $$\left\{u\in \mathbb{Z}_2^M\left|\exists T\subseteq S,\ \mathrm{s.t.}\ u = t_i \oplus \bigoplus_{v\in T} v\right.\right\}$$ 中，对应位为 $1$ 的下标序列的字典序最小的 01 串。

$1\le N, M, k\le 2000$

题解

字典序

处理最小化字典序问题，一个经典思路是按位贪心。在本题中，由于需要最小化的串长不固定，故贪心思路为：

• 如果 $u$ 可以为全零串，则答案即为全零串；否则，应使第一个为 $1$ 的下标尽可能小。
• 在确定第一个 $1$ 的下标后，检查是否可以将后缀全部变成 $0$，如果可以则输出；否则，应使第二个为 $1$ 的下标尽可能小。
• $\ldots$

上述贪心等价于：

• 如果 $u$ 可以为全零串，则答案即为全零串；否则，应尽量使第 1 位为 $1$。
• 如果确定第 1 位后，从第 2 位起可以为全零，则输出；否则，应尽量使第 12 位为 $1$。
• $\ldots$

我会线性基

因为涉及到异或，不难想到用线性基来处理本题。假设我们已经将 $S$ 处理成了相应的基向量。

对于每个询问，首先把所有主元清零，使得询问串最多只有自由元的位置非零。如果此时询问串变成全零串，则答案即为全零串。

否则，按主元顺序处理每个基向量。需要再次异或上一个基向量，当且仅当异或可以使询问串主元对应位置变成 $1$（也即此时询问串主元位置为 $0$）。特别地，如果异或完，主元位置之后变成全零，则答案即为当前串。

使用 bitset 处理，复杂度即为 $O(NMQ/w)$, 其中 $w$ 表示 bitset 位长。

除上述做法以外，还有各种使用线性基的处理方式，在此不详细展开。

不推荐考场实现的做法（简要版）

得到线性基之后，可以考虑补充没有主元对应的标准基，这样可以得到 $\mathbb{Z}_2^M$ 的一组基 $B$。将询问在 $B$ 下分解，则答案为全零串当且仅当补充的标准基的系数为 $0$。

检查完一个 $S$ 的主元位置 $x$ 后，如果这一位之后没有非零自由元，则输出当前串；否则，为了在子空间 $\mathbb{Z}_2^{M-x}$ 中处理询问串的后 $(M-x)$ 位，需要将 $x$ 对应的基向量（去掉主元的 $1$ 之后）在该子空间中重新分解，更新系数。

English version

Firstly, consider a classical dp to calculate $dp_{u,k}$ as the number of delete $k$ vertices in subtree $u$ without considering deleting vertex $n-i+1$ everyday. This is trivial.

Then, due to the existence of an “automatic deletion” process, we cannot view the selected points within the subtree of $u$ as operations with only relative order, because they may be illegal. However, we consider the final operation sequence, putting the vertex chosen on the $i$ th day in the position $n-i+1$. That is, if we firstly choose $4$, then $3$, then $1$, it will be $0431$. Then, one vertex $u$ must be put in position $u$ or later.

Then, we find that for the subtree of vertex $u$ with DFS order interval $[l,r]$, all vertex can't be put in position before $l$, and always legal to put in position after $r$ if parent-child relations are satisfied.

So we consider a dp $f_{u,i,j,k}$ which represents that the subtree of $u$ leaves position $i$ for ancestors (which means nothing can be placed at position $i$ or before, and if $i=0$, then nothing is left for ancestors), there are $j$ empty spaces (not including the one left for ancestors), and $k$ vertices need to be put into positions after the subtree of $u$. In the $i=0$ case,we merge subtrees,and the subtree with smaller DFS order can put some backward operations into the space of the subtree with bigger DFS order.

Specifically, consider the sons of $u$ enumerated in reverse order of DFS, and the son is $v$.Then enumerate $w$ as how many backward operations from $v$ will fill in space of $u$. The transition is $f_{u,0,j+j1-w,k+k1-w} \leftarrow f_{u,0,j+j1-w,k+k1-w}+f_{u,0,j,k}\times f_{v,0,j1,k1}\times {j \choose w}\times{k+k1-w \choose k}$.

For $f_{v,i,j,k}(i\neq 0)$, it won't interfere the transition with its following siblings. And for $f_{u,i,j,k}$, just consider where to put $u$. The answer for $i$ operations is $f_{1,i,i-2,0}$.

中文版本

对于树上选一个点删去一个子树方案数这个经典问题，一个常见的 dp 是记 $dp_{u,k}$ 为 $u$ 子树选 $k$ 个点方案数，转移时兄弟间用组合数将其合并，然后祖先要选就必须选在它们前面，这一部分 $O(n^2)$。

回到本题，由于存在“自动删点”的过程因此我们不能将 $u$ 子树内选的点看成只有相对顺序的操作，因为其可能不合法。但我们考虑最终的操作序列，没有的位置留空：比如样例 $1$ 中第一次选 $4$，第二次选 $3$，第三次选 $1$，那么操作序列即为 $0 4 3 1$。也就是第 $i$ 次选的点放在 $n-i+1$ 的位置上。这样，我们发现一个点 $u$ 只能填在 $u$ 及以后的位置，那么对于一个点 $u$ 的子树，其 dfs 序区间为 $[l,r]$，那么 $u$ 子树的点填到 $r$ 以后的位置一定合法，而 $u$ 留的空其前面的兄弟和祖先填进去只要没有父子关系干扰一定合法，于是我们考虑 dp。

考虑一个 dp $f_{u,i,j,k}$ 表示 $u$ 子树 $i$ 这个位置留给祖先（也就是说 $i$ 及以前不能放东西，如果 $i=0$ 就不留），有 $j$ 个空（不包含给祖先留的），有 $k$ 个点要填到 $u$ 子树以后的位置。先考虑 $i=0$ 情况。那么合并两个子树的时候就是 dfs 序更小的子树可以选一些向后的操作填到 dfs 序更大子树的空里面。然后两个子树的空合并，向后操作合并。

具体来说，考虑 $u$ 的儿子按 dfs 序倒序枚举，对于一个儿子 $v$，那么合并 $f_{u,0,j,k}$ 和 $f_{v,0,j1,k1}$ 的时候先枚举一个 $w$ 代表选多少个 $v$ 中的向后操作填到 $u$ 的 $v$ 之后的子树，转移即为 $f_{u,0,j+j1-w,k+k1-w}\leftarrow f_{u,0,j+j1-w,k+k1-w}+f_{u,0,j,k}\times f_{v,0,j1,k1}\times {j \choose w}\times{k+k1-w \choose k}$。

再考虑 $f_{v,i,j1,k1}$ ，发现它需要给祖先留空并不影响其和后面兄弟的转移，因此转移同上，只是 $v$ 留的空 $u$ 同样需要留，所以转移到 $f_{u,i,j+j1-w,k+k1-w}$。注意这里需要预处理转移系数（因为 $i$ 取任何值转移系数相同）才能达到 $O(n^5)$。

然后考虑 $f_{u,i,j,k}$ 的转移，即 $v$ 后面的子树已经留了空。那么 $v$ 子树现在不能放任何东西，但是可以用一些向后的操作填 $i$ 后面的空，这里用 $dp_{v,k}$ 去转移即可。

子树转移完后，接下来是 $u$ 自身的操作。$u$ 可以有几种选择：

• 不填，那么会多一个空 $f_{u,i,j,k}\rightarrow f_{u,i,j+1,k}$，如果把这个空留给祖先填，那么 $f_{u,0,j,k}\rightarrow f_{u,dfn_u,j,k}$。
• 填到子树准备的空里面，此时有两种选择：一是不再给祖先留空，那么 $f_{u,i,j,k}\rightarrow f_{u,0,j+1,k}$，一种是在 $i$ 前面重新给祖先留一个空，那么 $f_{u,i,j,k}\rightarrow f_{u,i_1,j+1,k}(i_1 < i)$。
• 填自己，此时不能给上面留空，$f_{u,0,j,k}$ 不变。
• 让自己变为向后操作，那么 $u$ 子树内现在不能填任何东西，但是可以给祖先留空，$f_{u,i,siz_u-2,k}\rightarrow f_{u,i,siz_u-1,k+1},f_{u,0,siz_u-1,k}\rightarrow f_{u,0,siz_u,k+1}$。

最后求答案的时候，对于要求 $k$ 次操作，相当于给 $1$ 在 $n-k+1$ 的位置留了空，同时恰好只有 $n-k$ 个空（那么后面就没有空，就是合法的操作序列），输出即可。

English version

Firstly, consider a classical dp to calculate $dp_{u,k}$ as the number of delete $k$ vertices in subtree $u$ without considering deleting vertex $n-i+1$ everyday. This is trivial.

Then, due to the existence of an “automatic deletion” process, we cannot view the selected points within the subtree of $u$ as operations with only relative order, because they may be illegal. However, we consider the final operation sequence, putting the vertex chosen on the $i$ th day in the position $n-i+1$. That is, if we firstly choose $4$, then $3$, then $1$, it will be $0431$. Then, one vertex $u$ must be put in position $u$ or later.

Then, we find that for the subtree of vertex $u$ with DFS order interval $[l,r]$, all vertex can't be put in position before $l$, and always legal to put in position after $r$ if parent-child relations are satisfied.

So we consider a dp $f_{u,i,j,k}$ which represents that the subtree of $u$ leaves position $i$ for ancestors (which means nothing can be placed at position $i$ or before, and if $i=0$, then nothing is left for ancestors), there are $j$ empty spaces (not including the one left for ancestors), and $k$ vertices need to be put into positions after the subtree of $u$. In the $i=0$ case,we merge subtrees,and the subtree with smaller DFS order can put some backward operations into the space of the subtree with bigger DFS order.

Specifically, consider the sons of $u$ enumerated in reverse order of DFS, and the son is $v$.Then enumerate $w$ as how many backward operations from $v$ will fill in space of $u$. The transition is $f_{u,0,j+j1-w,k+k1-w} \leftarrow f_{u,0,j+j1-w,k+k1-w}+f_{u,0,j,k}\times f_{v,0,j1,k1}\times {j \choose w}\times{k+k1-w \choose k}$.

For $f_{v,i,j,k}(i\neq 0)$, it won't interfere the transition with its following siblings. And for $f_{u,i,j,k}$, just consider where to put $u$. The answer for $i$ operations is $f_{1,i,i-2,0}$.

中文版本

对于树上选一个点删去一个子树方案数这个经典问题，一个常见的 dp 是记 $dp_{u,k}$ 为 $u$ 子树选 $k$ 个点方案数，转移时兄弟间用组合数将其合并，然后祖先要选就必须选在它们前面，这一部分 $O(n^2)$。

回到本题，由于存在“自动删点”的过程因此我们不能将 $u$ 子树内选的点看成只有相对顺序的操作，因为其可能不合法。但我们考虑最终的操作序列，没有的位置留空：比如样例 $1$ 中第一次选 $4$，第二次选 $3$，第三次选 $1$，那么操作序列即为 $0 4 3 1$。也就是第 $i$ 次选的点放在 $n-i+1$ 的位置上。这样，我们发现一个点 $u$ 只能填在 $u$ 及以后的位置，那么对于一个点 $u$ 的子树，其 dfs 序区间为 $[l,r]$，那么 $u$ 子树的点填到 $r$ 以后的位置一定合法，而 $u$ 留的空其前面的兄弟和祖先填进去只要没有父子关系干扰一定合法，于是我们考虑 dp。

考虑一个 dp $f_{u,i,j,k}$ 表示 $u$ 子树 $i$ 这个位置留给祖先（也就是说 $i$ 及以前不能放东西，如果 $i=0$ 就不留），有 $j$ 个空（不包含给祖先留的），有 $k$ 个点要填到 $u$ 子树以后的位置。先考虑 $i=0$ 情况。那么合并两个子树的时候就是 dfs 序更小的子树可以选一些向后的操作填到 dfs 序更大子树的空里面。然后两个子树的空合并，向后操作合并。

具体来说，考虑 $u$ 的儿子按 dfs 序倒序枚举，对于一个儿子 $v$，那么合并 $f_{u,0,j,k}$ 和 $f_{v,0,j1,k1}$ 的时候先枚举一个 $w$ 代表选多少个 $v$ 中的向后操作填到 $u$ 的 $v$ 之后的子树，转移即为 $f_{u,0,j+j1-w,k+k1-w}\leftarrow f_{u,0,j+j1-w,k+k1-w}+f_{u,0,j,k}\times f_{v,0,j1,k1}\times {j \choose w}\times{k+k1-w \choose k}$。

再考虑 $f_{v,i,j1,k1}$ ，发现它需要给祖先留空并不影响其和后面兄弟的转移，因此转移同上，只是 $v$ 留的空 $u$ 同样需要留，所以转移到 $f_{u,i,j+j1-w,k+k1-w}$。注意这里需要预处理转移系数（因为 $i$ 取任何值转移系数相同）才能达到 $O(n^5)$。

然后考虑 $f_{u,i,j,k}$ 的转移，即 $v$ 后面的子树已经留了空。那么 $v$ 子树现在不能放任何东西，但是可以用一些向后的操作填 $i$ 后面的空，这里用 $dp_{v,k}$ 去转移即可。

子树转移完后，接下来是 $u$ 自身的操作。$u$ 可以有几种选择：

• 不填，那么会多一个空 $f_{u,i,j,k}\rightarrow f_{u,i,j+1,k}$，如果把这个空留给祖先填，那么 $f_{u,0,j,k}\rightarrow f_{u,dfn_u,j,k}$。
• 填到子树准备的空里面，此时有两种选择：一是不再给祖先留空，那么 $f_{u,i,j,k}\rightarrow f_{u,0,j+1,k}$，一种是在 $i$ 前面重新给祖先留一个空，那么 $f_{u,i,j,k}\rightarrow f_{u,i_1,j+1,k}(i_1 < i)$。
• 填自己，此时不能给上面留空，$f_{u,0,j,k}$ 不变。
• 让自己变为向后操作，那么 $u$ 子树内现在不能填任何东西，但是可以给祖先留空，$f_{u,i,siz_u-2,k}\rightarrow f_{u,i,siz_u-1,k+1},f_{u,0,siz_u-1,k}\rightarrow f_{u,0,siz_u,k+1}$。

最后求答案的时候，对于要求 $k$ 次操作，相当于给 $1$ 在 $n-k+1$ 的位置留了空，同时恰好只有 $n-k$ 个空（那么后面就没有空，就是合法的操作序列），输出即可。

简要题意

对于三个长度为 $n$ 的 01 字符串 $s_1,s_2,s_3$，称长度为 $n$ 的 01 字符串 $t$ 是好的当且仅当 $\forall 1 \le i,j \le n, \exists k \in \{1,2,3\}, s_{k,i} = t_i, s_{k,j} = t_j$。设 $f(s_1,s_2,s_3)$ 为这样的好的串的数量。

现在我们有三个长度为 $n$ 的随机 01 字符串 $s_1,s_2,s_3$，其中 $s_i (1 \le i \le 3)$ 的第 $j (1 \le j \le n)$ 个字符有 $\frac{p_{i,j}}{9}$ 的概率为 1，$\left(1 - \frac{p_{i,j}}{9}\right)$ 的概率为 0，其中 $p_{i,j}$ 是一个 $0$ 至 $9$ 的整数。所有的随机事件是独立的。你需要求 $f(s_1,s_2,s_3)$ 的期望，对 $998244353$ 取模。

$n \le 3 \times 10^5$

解法

引理：设 $\text{maj}(a,b,c)$ 为 $a,b,c$ 中的众数；对于三个长度为 $n$ 的 01 字符串 $s_1,s_2,s_3$，设 $\text{maj}(s_1,s_2,s_3)$ 为长度为 $n$ 的字符串 $t$，其中 $t_i = \text{maj}(s_{1,i},s_{2,i},s_{3,i})$，则 $f(s_1,s_2,s_3) = |\{s_1,s_2,s_3,\text{maj}(s_1,s_2,s_3)\}|$。

我们首先说明以上四个字符串均满足题设条件。$s_1,s_2,s_3$ 满足条件是显然的。

对于 $t=\text{maj}(s_1,s_2,s_3)$，对于任意 $1 \le i < j \le n$，存在下标 $1 \le a < b \le 3$ 满足 $s_{a,i} = s_{b,i} = t_i$，又存在 $1 \le c < d \le 3$ 满足 $s_{c,j} = s_{d,j} = t_j$。根据抽屉原理 $\{a,b,c,d\}$ 中有两个数相等，对应的下标即是满足题设条件的 $k$。

接下来我们说明不存在其它字符串满足条件。当满足条件的字符串 $t$ 不等于 $\text{maj}(s_1,s_2,s_3)$ 时，设 $t_i \ne \text{maj}(s_1,s_2,s_3)_i$，则 $t_i$ 只在 $s_{1,i},s_{2,i},s_{3,i}$ 中出现恰好一次（不能不出现，否则不可能满足题设条件），不妨假设其为 $s_{1,i}$。此时取任意 $j \ne i$，根据题设条件必然有 $t_j = s_{1,j}$（因为 $k$ 必须取 $1$），因此 $t = s_1$。

进一步地，可以分类讨论得到 $|\{s_1,s_2,s_3,\text{maj}(s_1,s_2,s_3)\}| = 4 - \sum_{i=1}^3 [\text{maj}(s_1,s_2,s_3) = s_i]$：

• $f(s_1,s_2,s_3) = 4$ 时四个字符串两两不同；
• $f(s_1,s_2,s_3) = 3$ 时必然是某个 $s_i = \text{maj}(s_1,s_2,s_3)$ 的情况而不是 $s_i = s_j$ 的情况，因为 $s_i = s_j$ 会直接导致 $\text{maj}(s_1,s_2,s_3) = s_i$；
• $f(s_1,s_2,s_3) = 2$ 时必然是 $s_i = s_j = \text{maj}(s_1,s_2,s_3)$ 且剩余的字符串跟它们不同的情况；
• $f(s_1,s_2,s_3) = 1$ 时必然是四个字符串相等的情况。

由于期望的线性性，只需要计算 $\Pr[\text{maj}(s_1,s_2,s_3) = s_i]$ 即可。由于每一位的随机事件是独立的，所以直接把每一位相等的概率乘起来就行了。

复杂度 $O(n)$。

题外话

• 本题中文名“石墨烯”纯属出题人夹带私货，与题目无关，具体含义不便透露，大家不要过度解读。
• 本题原来只有 $k=0$ 这个版本作为签到，但是因为某些原因需要稍微加强难度，就变成了现在这个版本。

Description

• 给定长为 $n$ 的序列 $a, b$，每轮操作先使每对 $(a_i, b_i)$ 中较小值变为零，较大值变为它们的差，然后使 $a$ 循环右移一位。
• 操作开始前，可以先对 $a$ 进行 $k$ 次 $a_i \leftarrow a_{i-1}$（需保证 $a_i$ 恒非负），问最少几轮操作才能使 $a$ 全变为零？
• $1 \le n, \sum{n} \le 5 \times 10^5$，$1 \le a_i, b_i \le 10^9$。

$k=0$

• 考虑对于每个 $a_i$ 分别求出至少循环右移几次之后会变为零，记之为 $d_i$，则答案即为 $\max_{1≤\le i \le n}{d_i}$。
• 遇到环上问题，首先考虑断环为链（即令 $a_{i+n}=a_i,b_{i+n}=b_i$）。

• 考虑如下转化：记 $s$ 为由 $a_1$ 个左括号，$b_1$ 个右括号，$a_2$ 个左括号，$b_2$ 个右括号，……，$a_{2n}$ 个左括号，$b_{2n}$ 个右括号顺次拼接而成的括号串，则原题中的操作过程就相当于对 $s$ 进行括号匹配的过程，而 $a_i$ 会被哪个 $b_j$ 首次消成零，就取决于 $a_i$ 对应的第一个左括号所匹配的右括号属于哪个 $b_j$ 。

  • “使 $(a_i, b_i)$ 中较小值变为零，较大值变为它们的差” $\rightarrow$ “匹配 $a_i, b_i$ 对应的括号”；
  • “使 $a$ 循环右移一位” $\rightarrow$ “未被匹配的左括号继续向右寻找右括号尝试匹配”。
• 对于括号匹配问题，自然想到利用前缀和转化。
• 令 $c_i=\sum_{j=1}^{i}(a_i-b_j)$，记 $p_i$ 为最小的满足 $p_i > i$ 且 $c_{p_i} \le c_i$ 的下标，则 $d_i$ 即为 $p_i-i$。
• 使用单调栈即可求出所有 $p_i$，时间复杂度为 $O(\sum n)$。

正解

• 加入了 $k$ 的限制后，考虑二分答案 $x$，转而求在 $x$ 轮操作后将 $a$ 全变为零的最少 $-1$ 次数。
• 发现直接在断环为链的 $2n$ 个数上不太好计算贡献（因为可能会重复计算），所以我们进行如下调整：将 $a,b$ 同时循环右移若干位，使得 $a_i-b_i$ 的前缀和 $c_i$ 的最小值在 $c_n$ 处取到。
• 这样调整的好处是，对于调整后的 $a,b$，我们所关心的 $p_i(1 \le i \le n)$ 都不会超过 $n$，也就是说，在实际操作过程中，不会出现 $a_n > 0$ 右移到 $a_1$ 的情况。
• 因此，我们仅通过调整 $a, b$ 就将环上问题转化为了一个长为 $n$ 的链上问题。
• 接下来考虑如何在调整后的 $a,b$ 上计算答案为 $x$ 时的最少 $-1$ 次数。
• 不难想到对 $a$ 从 $n-x$ 到 $0$ 使用贪心，若当前位置 $i$ 对应的 $d_i=p_i-i > x$，即若 $\min_{j=i+1}^{i+x}{c_j} > c_i$，则对 $a_{i+1}$ 进行 $\min_{j=i+1}^{i+x}{c_j} - c_i$ 次 $-1$。
• 整个过程均可通过单调栈维护。
• 时间复杂度为 $O(\sum n \log k)$。