310722: CF1876B. Effects of Anti Pimples

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

B. Effects of Anti Pimplestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Chaneka has an array $[a_1,a_2,\ldots,a_n]$. Initially, all elements are white. Chaneka will choose one or more different indices and colour the elements at those chosen indices black. Then, she will choose all white elements whose indices are multiples of the index of at least one black element and colour those elements green. After that, her score is the maximum value of $a_i$ out of all black and green elements.

There are $2^n-1$ ways for Chaneka to choose the black indices. Find the sum of scores for all possible ways Chaneka can choose the black indices. Since the answer can be very big, print the answer modulo $998\,244\,353$.

Input

The first line contains a single integer $n$ ($1 \leq n \leq 10^5$) — the size of array $a$.

The second line contains $n$ integers $a_1,a_2,a_3,\ldots,a_n$ ($0\leq a_i\leq10^5$).

Output

An integer representing the sum of scores for all possible ways Chaneka can choose the black indices, modulo $998\,244\,353$.

ExamplesInput
4
19 14 19 9
Output
265
Input
1
0
Output
0
Input
15
90000 9000 99000 900 90900 9900 99900 90 90090 9090 99090 990 90990 9990 99990
Output
266012571
Note

In the first example, below are the $15$ possible ways to choose the black indices:

  • Index $1$ is black. Indices $2$, $3$, and $4$ are green. Maximum value among them is $19$.
  • Index $2$ is black. Index $4$ is green. Maximum value among them is $14$.
  • Index $3$ is black. Maximum value among them is $19$.
  • Index $4$ is black. Maximum value among them is $9$.
  • Indices $1$ and $2$ are black. Indices $3$ and $4$ are green. Maximum value among them is $19$.
  • Indices $1$ and $3$ are black. Indices $2$ and $4$ are green. Maximum value among them is $19$.
  • Indices $1$ and $4$ are black. Indices $2$ and $3$ are green. Maximum value among them is $19$.
  • Indices $2$ and $3$ are black. Index $4$ is green. Maximum value among them is $19$.
  • Indices $2$ and $4$ are black. Maximum value among them is $14$.
  • Indices $3$ and $4$ are black. Maximum value among them is $19$.
  • Indices $1$, $2$, and $3$ are black. Index $4$ is green. Maximum value among them is $19$.
  • Indices $1$, $2$, and $4$ are black. Index $3$ is green. Maximum value among them is $19$.
  • Indices $1$, $3$, and $4$ are black. Index $2$ is green. Maximum value among them is $19$.
  • Indices $2$, $3$, and $4$ are black. Maximum value among them is $19$.
  • Indices $1$, $2$, $3$, and $4$ are black. Maximum value among them is $19$.

The total sum is $19+14+19+9+19+19+19+19+14+19+19+19+19+19+19 = 265$.

Output

题目大意：
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 \leq 10^5$$）。

输出：
- 一个整数，代表Chaneka选择黑色索引的所有可能方式的得分总和，模$$998,244,353$$。

示例：
输入：
```
4
19 14 19 9
```
输出：
```
265
```

注意：
在第一个示例中，以下是选择黑色索引的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。题目大意： 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 \leq 10^5$$）。 输出： - 一个整数，代表Chaneka选择黑色索引的所有可能方式的得分总和，模$$998,244,353$$。 示例： 输入： ``` 4 19 14 19 9 ``` 输出： ``` 265 ``` 注意： 在第一个示例中，以下是选择黑色索引的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。

Source/Category

加入题单

上一题 下一题 算法标签：