CF1988F Heartbeat

对于一个数组 $u_1, u_2, \ldots, u_n$，定义如下： - 前缀最大值：如果下标 $i$ 满足 $u_i > u_j$ 对于所有 $j < i$，则称 $i$ 是一个前缀最大值； - 后缀最大值：如果下标 $i$ 满足 $u_i > u_j$ 对于所有 $j > i$，则称 $i$ 是一个后缀最大值； - 上升点：如果下标 $i$（$i > 1$）满足 $u_i > u_{i-1}$，则称 $i$ 是一个上升点。 你会得到三个代价数组：$[a_1, a_2, \ldots, a_n]$，$[b_1, b_2, \ldots, b_n]$，以及 $[c_0, c_1, \ldots, c_{n-1}]$。 定义一个数组的代价为 $a_x \cdot b_y \cdot c_z$，其中 $x$ 是前缀最大值的个数，$y$ 是后缀最大值的个数，$z$ 是上升点的个数。 设 $f(n)$ 为 $1,2,\ldots,n$ 的所有排列的代价之和。请你求出 $f(1), f(2), \ldots, f(n)$，并对 $998\,244\,353$ 取模。

第一行包含一个整数 $n$（$1 \le n \le 700$）。 第二行包含 $n$ 个整数 $a_1, \ldots, a_n$（$0 \le a_i < 998\,244\,353$）。 第三行包含 $n$ 个整数 $b_1, \ldots, b_n$（$0 \le b_i < 998\,244\,353$）。 第四行包含 $n$ 个整数 $c_0, \ldots, c_{n-1}$（$0 \le c_i < 998\,244\,353$）。

输出 $n$ 个整数，第 $i$ 个数表示 $f(i)$ 对 $998\,244\,353$ 取模的结果。

在第二个样例中： - 考虑排列 $[1,2,3]$。下标 $1,2,3$ 都是前缀最大值。下标 $3$ 是唯一的后缀最大值。下标 $2,3$ 是上升点。因此，该排列的代价为 $a_3 b_1 c_2 = 12$。 - 排列 $[1,3,2]$ 有 $2$ 个前缀最大值，$2$ 个后缀最大值，$1$ 个上升点。其代价为 $6$。 - 排列 $[2,1,3]$ 有 $2$ 个前缀最大值，$1$ 个后缀最大值，$1$ 个上升点。其代价为 $4$。 - 排列 $[2,3,1]$ 有 $2$ 个前缀最大值，$2$ 个后缀最大值，$1$ 个上升点。其代价为 $6$。 - 排列 $[3,1,2]$ 有 $1$ 个前缀最大值，$2$ 个后缀最大值，$1$ 个上升点。其代价为 $3$。 - 排列 $[3,2,1]$ 有 $1$ 个前缀最大值，$3$ 个后缀最大值，$0$ 个上升点。其代价为 $3$。 所有排列的代价之和为 $34$，因此 $f(3) = 34$。 由 ChatGPT 4.1 翻译