upd：修改一处笔误。

神仙 Kubic 的思路真的简洁而自然，我这种小蒟蒻也能看明白 qwq。

（Kubic 为什么这么强大？Kubic 为什么这么强大？Kubic 为什么这么强大？Kubic 为什么这么强大？Kubic 为什么这么强大？Kubic 为什么这么强大？Kubic 为什么这么强大？Kubic 为什么这么强大？Kubic 为什么这么强大？Kubic 为什么这么强大？Kubic 为什么这么强大？）

先将 $s,t$ 升序排序，定义 $a_i$ 表示最小的能和第 $i$ 头牛匹配的牛棚，$b_i$ 表示最小的能和第 $i$ 个牛棚匹配的牛。

假设最小的未被匹配的牛为 $p$，则「极大匹配」的充要条件为 $s_p\gt t_{a_p}$。

考虑枚举这个最小未被匹配的牛，设其编号为 $i$。

不难发现，$[a_i,n]$ 范围内的牛棚必须被匹配，否则 $i$ 一定可以和 $a_i$ 匹配。

$1\sim i-1$ 的牛必然能和 $[a_i,n]$ 内的牛棚匹配，$i+1\sim n$ 的牛则不一定。

考虑枚举 $1\sim i-1$ 匹配到 $[a_i,n]$ 内的牛棚的数量为 $j$，那么就需要 $1\sim i-1$ 未被匹配的牛全部与 $[1,a_i)$ 内的某个牛棚匹配（根据条件），$i+1\sim n$ 的某些牛和 $[a_i,n]$ 内未被匹配的 $n-a_i+1-j$ 个牛棚匹配。

这个问题并不难解决。设 $f_{i,j}$ 表示前 $i$ 个牛棚和 $j$ 头牛匹配的方案数，$g_{i,j}$ 表示后 $i$ 头牛和 $j$ 个牛棚匹配的方案数。

转移方程：$f_{i,j}=f_{i-1,j}+f_{i-1,j-1}\times \max\{0,b_i-j+1\},g_{i,j}=g_{i+1,j}+g_{i+1,j-1}\times \max\{n-a_i-j+2,0\}$。

则上述方案总数可以表示为 $g_{i+1,n-a_i+1-j}\times f_{a_i-1,i-j-1}\times j!$。

最后不要忘了加上 $f_{n,n}$，表示「完美匹配」的方案数。

不会写的做法，不保证正确：

首先发现前缀后缀是否相等可以直接哈希判断，那么这个问题就化为了求 $s_{i+1\sim n-i}$ 的 border。

我并没有发现这个东西可以类 KMP 势能分析均摊 $\mathcal O(1)$ 计算的性质，但是我学过一点点后缀数组，知道 LCP（最长公共前缀）的一个性质：

$$\forall 1\le i\lt j\lt k\le n,\text{LCP}(sa_i,sa_k)=\min\{\text{LCP}(sa_i,sa_j),\text{LCP}(sa_j,sa_k)\}$$

把 $\gt \lceil \frac{n}{2} \rceil$ 的 $sa$ 值标记一下，从前往后递推一遍，得到每个 $sa_i$ 前面第一个被标记过的 $sa$，用 RMQ 求值即可。

时间复杂度 $\mathcal O(n\log n)$，后缀数组常数卡小点估计能过，但一点也不精妙。

定义 $f_i$ 表示 $s_{i+1\sim n-i}$ 的最长不重叠公共前后缀长度。

当我们从大到小枚举 $i$，显然有 $f_i\le f_{i+1}+2$。

从洛谷题解搬的一张图：

那么我们不妨令 $f_i=f_{i+1}+2$，用哈希判合法性，不合法时暴力往前跳。

和 KMP 类似，势能总和为 $n$，那么总的时间复杂度就是 $\mathcal O(n)$。

很有启发的一道题，从中认识到，不能忽视原题中某些「显而易见」的性质，认真分析，它们有可能就是通往正解的钥匙。

首先不难想到BFS。

以及，箱子能被推动到目标方向当且仅当：①目标方向是空地；②目标方向关于箱子的对面是空地，且人能到达。

如果允许人在空地上任意传送，本题将会简单很多。令 $f_{i,j}$ 表示箱子到达 $(i,j)$ 时的最小次数，每次转移只需判断目标方向的对面是否是空地即可。

但有了沉重货物的限制，会导致人并不一定能到达箱子旁的空地（即使初始时他可以到达）。

不过不难发现，当人推动一次箱子时，他将会“取代”箱子原本的位置。也就是说，判断人是否能到达空地，实际上是判断箱子上次的位置是否能到达那里。而方向只有四个，令 $f_{i,j,0/1/2/3}$ 表示箱子到达 $(i,j)$ ，且上次它在现在的 上/下/左/右 时的最小次数。每次转移时，从上次的位置出发进行搜索，判断是否能到达目标方向对面的空地即可。

时间复杂度大常数$O(n^4)$，无法通过。

上述算法的瓶颈在于，每次转移时都要进行一次搜索，包含了大量的重复计算。我们希望通过一些预处理优化这一过程。

实际上已经很明显了。我们把每个空地抽象成点，向四周的空地连边。箱子放于 $(x,y)$ 时人无法从 $(a,b)$ 到达 $(c,d)$ ，实际上就是说 $(x,y)$ 是原图的一个割点，将 $(a,b)$ 所在连通块与 $(c,d)$ 所在连通块分离。相反，若 $(a,b)$ 与 $(c,d)$ 在同一连通块中，人肯定能相互到达。这样，通过预处理原图的相关$dcc$信息，我们可以做到$O(1)$的转移。

关于 $f$ 的初始化，需要从人的出发点单独搜一次，记录初始时人能到达的箱子旁的空地。

码量稍大，不过每一部分相对简单。

COGS的这一题是超级满配版本

比洛谷的要强力的多：894. 追查坏牛奶 - COGS

额外要求是：求出最小割流量，同时求出割边最小，同时字典序最小的方案

输出割掉的边

最小割流量好求，最小割边的数量也好求，但同时确定哪条边不太好弄，因为存在方法互斥

首先：最小割流量就是跑最大流的结果

求最小割边的数量，需要在刚刚跑完最大流的网络上

把所有的满流边流量重新标记为1，不满流的重新标记为INF

在新的网络上跑一次最大流

这个时候得到的流量就是最小割边的数量

正确性：

满流边一定是某条流量通路的瓶颈路(虽然不一定是唯一瓶颈路)

把满流的边标记成1去跑增广路

得到的结果就是没有公共边的流量通路的条数(因为公共边只允许通过1点流量被计算一次)

那么就给这这些流量通路每个断开一条边即可(如果存在公共边先断开公共边)

如何求最小字典序的方案：

在最小割的情况下

首先要记住，我们一定是优先断开边权最大的必须满流边(删去这条边后，重新对整个网络跑最大流，最大流量会减小这个边的边权那么多(也就是这条边的传递作用无可替代))

那么找最小字典序方案也出来了：在正常的图上，先跑一次最大流

然后枚举所有边（首先把边按照边权(大到小)-字典序(小到大)两个关键字排序）

先复原整个网络到未增广形态

然后尝试删去这条边，看最大流结果减少的是否是这条边流量那么多

如果是，说明这是关键边，记录这条边会被删除(贪心保证了删除的边数目最少，因为这条边满流，不删它就要删和它在同一支流的多条边) 把这条边永久性删除，并将最大流的结果减小(该边的流量)那么多

这就导致你需要先用正常的边权跑DINIC，再用1和INF的边权跑DINIC，再用正常的边权去找应当被删除的边