← 返回题目列表

Codeforces · 2206/L

L. 洋葱

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

洋葱广泛用于世界各地的美食中。这道题是关于几何学中的“洋葱皮”过程。

二维平面中的一组点是 凸 如果对于集合中的任意一对点 $$$p$$$ 和 $$$q$$$,连接 $$$p$$$ 和 $$$q$$$ 的线段完全包含在集合中。对于一组点 $$$S$$$,其 凸包 是包含 $$$S$$$ 中所有点的最小凸集。

给定四个整数 $$$n$$$、$$$a$$$、$$$b$$$ 和 $$$k$$$。您有一组 $$$S$$$ 的 $$$n$$$ 点,初始化如下: $$S = \{ (x, (ax + b) \bmod n) \mid x = 0, 1, \ldots, n-1 \}.$$

您应用以下操作 $$$k$$$ 次:令 $$$H$$$ 为集合 $$$S$$$ 的凸包,然后从 $$$S$$$ 中删除位于凸包 $$$H$$$ 边界上的所有点。

请注意,$$$S$$$ 可以变为空。在这种情况下,它的凸包也是空的,并且它的面积为零。

对于每个操作,确定 翻倍 凸包的面积$$$H$$$。可以证明这个值始终是一个整数。

输入

输入由一行组成,其中包含四个整数 $$$n$$$、$$$a$$$、$$$b$$$ 和 $$$k$$$ ($$$1 \le n \le 10^9$$$; $$$0 \le a, b \lt n$$$; $$$1 \le k \le 300$$$)。

输出

输出 $$$k$$$ 行。第 $$$i$$$ 行应包含一个整数,表示第 $$$i$$$ 操作中凸包的双倍面积。

示例

输入
复制

4 1 2 1

输出
复制

8

输入
复制

37 14 7 5

输出
复制

2257
1406
592
74
0

输入
复制

280 40 12 4

输出
复制

131040
82880
39200
0

注意

示例输入/输出#1 的说明

图L.1说明了第一个操作中$$$S$$$中的点和凸包的边界。凸包的面积为 $$$4$$$,因此加倍面积为 $$$8$$$。

图 L.1:示例输入 #1 的图示。

示例输入/输出#2 的说明

图 L.2 说明了前四个操作的边界。第四次操作后,集合 $$$S$$$ 变空。第五次操作的区域是$$$0$$$。

图 L.2:示例输入 #2 的图示。