CF1081G Mergesort Strikes Back

Chouti 回忆起他刚开始学习竞赛编程的日子。当时他刚学会写归并排序，觉得归并排序太慢了，于是他限制了递归的最大深度，并将归并排序修改成如下形式：  Chouti 发现他的想法很愚蠢，因为显然这种“归并排序”有时无法正确地排序数组。然而，现在 Chouti 开始思考这种“归并排序”到底有多好。具体来说，Chouti 想知道对于 $1, 2, \ldots, n$ 的一个随机排列 $a$，调用 MergeSort(a, 1, n, k) 后，数组中逆序对的期望数量是多少。 可以证明，这个期望值是有理数。对于给定的质数 $q$，假设答案可以表示为 $\frac{u}{d}$，其中 $\gcd(u,d)=1$，你需要输出一个整数 $r$，满足 $0 \le r < q$ 且 $rd \equiv u \pmod q$。可以证明这样的 $r$ 存在且唯一。

第一行包含三个整数 $n, k, q$（$1 \leq n, k \leq 10^5, 10^8 \leq q \leq 10^9$，$q$ 是质数）。

输出一个整数 $r$。

在第一个样例中，所有可能的排列为 $[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]$。 当 $k=1$ 时，MergeSort(a, 1, n, k) 只会返回原始排列。因此答案为 $9/6=3/2$，你应输出 $499122178$，因为 $499122178 \times 2 \equiv 3 \pmod {998244353}$。 在第二个样例中，所有可能的排列为 $[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]$，对应的 MergeSort(a, 1, n, k) 输出分别为 $[1,2,3],[1,2,3],[2,1,3],[1,2,3],[2,3,1],[1,3,2]$。因此答案为 $4/6=2/3$，你应输出 $665496236$，因为 $665496236 \times 3 \equiv 2 \pmod {998244353}$。 由 ChatGPT 4.1 翻译