codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1876B.md (2783B)


      1 Source: https://codeforces.com/problemset/problem/1876/B
      2 
      3 B. Effects of Anti Pimples
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 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.
     22 
     23 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$.
     24 
     25 Input
     26 
     27 The first line contains a single integer $n$ ($1 \leq n \leq 10^5$) — the size of array $a$.
     28 
     29 The second line contains $n$ integers $a_1,a_2,a_3,\ldots,a_n$ ($0\leq a_i\leq10^5$).
     30 
     31 Output
     32 
     33 An integer representing the sum of scores for all possible ways Chaneka can choose the black indices, modulo $998\,244\,353$.
     34 
     35 Examples
     36 
     37 Input
     38 
     39 ```
     40 4
     41 19 14 19 9
     42 ```
     43 
     44 Output
     45 
     46 ```
     47 265
     48 ```
     49 
     50 Input
     51 
     52 ```
     53 1
     54 0
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 0
     61 ```
     62 
     63 Input
     64 
     65 ```
     66 15
     67 90000 9000 99000 900 90900 9900 99900 90 90090 9090 99090 990 90990 9990 99990
     68 ```
     69 
     70 Output
     71 
     72 ```
     73 266012571
     74 ```
     75 
     76 Note
     77 
     78 In the first example, below are the $15$ possible ways to choose the black indices:
     79 
     80 * Index $1$ is black. Indices $2$, $3$, and $4$ are green. Maximum value among them is $19$.
     81 * Index $2$ is black. Index $4$ is green. Maximum value among them is $14$.
     82 * Index $3$ is black. Maximum value among them is $19$.
     83 * Index $4$ is black. Maximum value among them is $9$.
     84 * Indices $1$ and $2$ are black. Indices $3$ and $4$ are green. Maximum value among them is $19$.
     85 * Indices $1$ and $3$ are black. Indices $2$ and $4$ are green. Maximum value among them is $19$.
     86 * Indices $1$ and $4$ are black. Indices $2$ and $3$ are green. Maximum value among them is $19$.
     87 * Indices $2$ and $3$ are black. Index $4$ is green. Maximum value among them is $19$.
     88 * Indices $2$ and $4$ are black. Maximum value among them is $14$.
     89 * Indices $3$ and $4$ are black. Maximum value among them is $19$.
     90 * Indices $1$, $2$, and $3$ are black. Index $4$ is green. Maximum value among them is $19$.
     91 * Indices $1$, $2$, and $4$ are black. Index $3$ is green. Maximum value among them is $19$.
     92 * Indices $1$, $3$, and $4$ are black. Index $2$ is green. Maximum value among them is $19$.
     93 * Indices $2$, $3$, and $4$ are black. Maximum value among them is $19$.
     94 * Indices $1$, $2$, $3$, and $4$ are black. Maximum value among them is $19$.
     95 
     96 The total sum is $19+14+19+9+19+19+19+19+14+19+19+19+19+19+19 = 265$.