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)$。

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