CF1876B.Effects of Anti Pimples

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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$ .

输入格式

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$ ).

输出格式

An integer representing the sum of scores for all possible ways Chaneka can choose the black indices, modulo $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

说明/提示

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$ .

首页