← 返回题目列表

Codeforces · 1988/F

F. 心跳

中文机器翻译题面 查看原题

对于数组 $$$u_1, u_2, \ldots, u_n$$$,定义

- 作为索引$$$i$$$的前缀最大值,使得$$$u_i>u_j$$$对于所有$$$j<i$$$;
- 作为索引$$$i$$$的后缀最大值,使得$$$u_i>u_j$$$对于所有$$$j>i$$$;
- 作为索引 $$$i$$$ ($$$i>1$$$) 的上升使得 $$$u_i>u_{i-1}$$$。

为您提供了三个成本数组:$$$[a_1, a_2, \ldots, a_n]$$$、$$$[b_1, b_2, \ldots, b_n]$$$ 和 $$$[c_0, c_1, \ldots, c_{n-1}]$$$。

将具有 $$$x$$$ 前缀最大值、$$$y$$$ 后缀最大值和 $$$z$$$ 上升的数组的成本定义为 $$$a_x\cdot b_y\cdot c_z$$$。

令 $$$1,2,\ldots,n$$$ 的所有排列的成本总和为 $$$f(n)$$$。求 $$$f(1)$$$, $$$f(2)$$$, ..., $$$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

3
1 1 1
1 1 1
1 1 1

输出 #1

1 2 6

输入 #2

3
1 2 3
2 3 1
3 1 2

输出 #2

6 13 34

输入 #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$$$ 为上升指数。总之,它具有 $$$3$$$ 前缀最大值、$$$1$$$ 后缀最大值和 $$$2$$$ 上升。因此,其成本为$$$a_3b_1c_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$$$。