← 返回题目列表

Codeforces · 1876/B

B. 抗粉刺的效果

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

Chaneka 有一个数组 $$$[a_1,a_2,\ldots,a_n]$$$。最初,所有元素都是白色的。 Chaneka 将选择一个或多个不同的索引,并将这些所选索引处的元素涂成黑色。然后,她将选择索引是至少一个黑色元素索引的倍数的所有白色元素,并将这些元素着色为绿色。之后,她的分数是所有黑色和绿色元素中 $$$a_i$$$ 的最大值。

Chaneka 有 $$$2^n-1$$$ 种选择黑色索引的方法。求 Chaneka 选择黑色指数的所有可能方式的分数总和。由于答案可能非常大,请打印对 $$$998\,244\,353$$$ 取模的答案。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — 数组 $$$a$$$ 的大小。

第二行包含 $$$n$$$ 整数 $$$a_1,a_2,a_3,\ldots,a_n$$$ ($$$0\leq a_i\leq10^5$$$)。

输出

一个整数,表示 Chaneka 选择黑色索引的所有可能方式的分数总和,以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

4
19 14 19 9

输出 #1

265

输入 #2

1
0

输出 #2

0

输入 #3

15
90000 9000 99000 900 90900 9900 99900 90 90090 9090 99090 990 90990 9990 99990

输出 #3

266012571

注意

在第一个示例中,以下是选择黑色索引的 $$$15$$$ 可能方法:

- 索引 $$$1$$$ 为黑色。索引 $$$2$$$、$$$3$$$ 和 $$$4$$$ 为绿色。其中最大值为$$$19$$$。
- 索引 $$$2$$$ 为黑色。索引 $$$4$$$ 为绿色。其中最大值为$$$14$$$。
- 索引 $$$3$$$ 为黑色。其中最大值为$$$19$$$。
- 索引 $$$4$$$ 为黑色。其中最大值为$$$9$$$。
- 索引 $$$1$$$ 和 $$$2$$$ 为黑色。索引 $$$3$$$ 和 $$$4$$$ 为绿色。其中最大值为$$$19$$$。
- 索引 $$$1$$$ 和 $$$3$$$ 为黑色。索引 $$$2$$$ 和 $$$4$$$ 为绿色。其中最大值为$$$19$$$。
- 索引 $$$1$$$ 和 $$$4$$$ 为黑色。索引 $$$2$$$ 和 $$$3$$$ 为绿色。其中最大值为$$$19$$$。
- 索引 $$$2$$$ 和 $$$3$$$ 为黑色。索引 $$$4$$$ 为绿色。其中最大值为$$$19$$$。
- 索引 $$$2$$$ 和 $$$4$$$ 为黑色。其中最大值为$$$14$$$。
- 索引 $$$3$$$ 和 $$$4$$$ 为黑色。其中最大值为$$$19$$$。
- 索引 $$$1$$$、$$$2$$$ 和 $$$3$$$ 为黑色。索引 $$$4$$$ 为绿色。其中最大值为$$$19$$$。
- 索引 $$$1$$$、$$$2$$$ 和 $$$4$$$ 为黑色。索引 $$$3$$$ 为绿色。其中最大值为$$$19$$$。
- 索引 $$$1$$$、$$$3$$$ 和 $$$4$$$ 为黑色。索引 $$$2$$$ 为绿色。其中最大值为$$$19$$$。
- 索引 $$$2$$$、$$$3$$$ 和 $$$4$$$ 为黑色。其中最大值为$$$19$$$。
- 索引 $$$1$$$、$$$2$$$、$$$3$$$ 和 $$$4$$$ 为黑色。其中最大值为$$$19$$$。

总金额为 $$$19+14+19+9+19+19+19+19+14+19+19+19+19+19+19 = 265$$$。