codeforces-scrape

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

1061C.md (1683B)


      1 Source: https://codeforces.com/problemset/problem/1061/C
      2 
      3 C. Multiplicity
      4 
      5 time limit per test
      6 
      7 3 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 You are given an integer array $a_1, a_2, \ldots, a_n$.
     22 
     23 The array $b$ is called to be a subsequence of $a$ if it is possible to remove some elements from $a$ to get $b$.
     24 
     25 Array $b_1, b_2, \ldots, b_k$ is called to be good if it is not empty and for every $i$ ($1 \le i \le k$) $b_i$ is divisible by $i$.
     26 
     27 Find the number of good subsequences in $a$ modulo $10^9 + 7$.
     28 
     29 Two subsequences are considered different if index sets of numbers included in them are different. That is, the values ​of the elements ​do not matter in the comparison of subsequences. In particular, the array $a$ has exactly $2^n - 1$ different subsequences (excluding an empty subsequence).
     30 
     31 Input
     32 
     33 The first line contains an integer $n$ ($1 \le n \le 100\,000$) — the length of the array $a$.
     34 
     35 The next line contains integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^6$).
     36 
     37 Output
     38 
     39 Print exactly one integer — the number of good subsequences taken modulo $10^9 + 7$.
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 2  
     47 1 2
     48 ```
     49 
     50 Output
     51 
     52 ```
     53 3
     54 ```
     55 
     56 Input
     57 
     58 ```
     59 5  
     60 2 2 1 22 14
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 13
     67 ```
     68 
     69 Note
     70 
     71 In the first example, all three non-empty possible subsequences are good: $\{1\}$, $\{1, 2\}$, $\{2\}$
     72 
     73 In the second example, the possible good subsequences are: $\{2\}$, $\{2, 2\}$, $\{2, 22\}$, $\{2, 14\}$, $\{2\}$, $\{2, 22\}$, $\{2, 14\}$, $\{1\}$, $\{1, 22\}$, $\{1, 14\}$, $\{22\}$, $\{22, 14\}$, $\{14\}$.
     74 
     75 Note, that some subsequences are listed more than once, since they occur in the original array multiple times.