CF2203F Binary Search with One Swap

考虑以下在一个长度为 $n$ 的数组 $a$ 中查找整数 $x$ 的算法，数组元素从 $1$ 到 $n$ 编号： 1. 初始化 $l = 1$ 和 $r = n$； 2. 如果 $l > r$，结束算法并报告未找到目标元素； 3. 计算 $m = \lfloor \frac{l + r}{2} \rfloor$； 4. 如果 $a_m = x$，结束算法并报告找到目标元素； 5. 如果 $a_m < x$，令 $l = m + 1$，否则令 $r = m - 1$； 6. 转到步骤 $2$。 可以证明，如果数组 $a$ 是非递减有序的，那么该算法一定能成功找到 $a$ 中的任意元素。 你的任务如下：对于给定的 $n$，考虑所有满足 $1 \le i < j \le n$ 的数对 $(i, j)$。对于每个这样的数对，你需要计算它的**优美度**——即如果我们取数组 $a = [1, 2, 3, \dots, n]$ 并交换元素 $a_i$ 和 $a_j$，那么上述算法能够成功找到的整数 $x$（从 $1$ 到 $n$）的数量。然后，对于每个 $k$ 从 $0$ 到 $n$，你需要输出 $p_k$——优美度为 $k$ 的数对数量。

输入仅有一行，包含一个整数 $n$（$3 \le n \le 5 \cdot 10^6$）。

输出 $n+1$ 个整数 $p_0, p_1, \dots, p_n$，其中 $p_k$ 是优美度为 $k$ 的数对 $(i, j)$ 的数量。

考虑 $n = 4$ 的示例： - 如果交换 $a_1$ 和 $a_2$，那么 $1$、$3$ 和 $4$ 可以被成功找到； - 如果交换 $a_1$ 和 $a_3$，那么 $2$ 和 $4$ 可以被成功找到； - 如果交换 $a_2$ 和 $a_3$，那么 $1$、$3$ 和 $4$ 可以被成功找到； - 如果交换 $a_1$ 和 $a_4$，那么 $2$ 和 $3$ 可以被成功找到； - 如果交换 $a_2$ 和 $a_4$，那么 $1$ 和 $4$ 可以被成功找到； - 如果交换 $a_3$ 和 $a_4$，那么 $1$、$2$ 和 $4$ 可以被成功找到。 由 DeepSeek V3.2 翻译