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

输入 #1

3
1 1 1
1 1 1
1 1 1

输出 #1

1 2 6

输入输出样例 #2

输入 #2

3
1 2 3
2 3 1
3 1 2

输出 #2

6 13 34

输入输出样例 #3

输入 #3

5
1 4 2 5 3
2 5 1 3 4
300000000 100000000 500000000 400000000 200000000

输出 #3

600000000 303511294 612289529 324650937 947905622

说明/提示

在第二个样例中：

• 考虑排列 $[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 翻译