| Fişierul intrare/ieşire: | aquilla.in, aquilla.out | Sursă | ONI 2026, Baraj Seniori, ziua 1 |
| Autor | Alexandru Lorintz | Adăugată de |  Ivan Andrei •IvanAndrei |
| Timp execuţie pe test | 1.5 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Aquilla
Se dă un şir de N perechi de numere naturale (di, vi), pentru i de la 1 la N.
Un subşir de indici 1 ≤ i1 < i2 < ... < ik ≤ N se numeşte şmecher dacă pentru oricare doi indici consecutivi ip şi ip + 1 (pentru orice 1 ≤ p < k) din acest subşir, diferenţa ip + 1 - ip este divizibilă cu min(dip, dip + 1).
Cerinţă
Să se determine suma produselor vi1 * vi2 * ... * vik pentru toate subşirurile şmechere nevide, modulo 109 + 7.
Date de intrare
Fişierul de intrare aquilla.in conţine pe prima linie numărul natural N. Pe a doua linie se află N numere naturale d1, d2, ..., dN, separate prin câte un spaţiu. Pe a treia linie se află N numere naturale v1, v2, ..., vN, separate prin câte un spaţiu.
Date de ieşire
Fişierul de ieşire aquilla.out va conţine pe o singură linie un număr natural, reprezentând suma produselor tuturor subşirurilor şmechere nevide, modulo 109 + 7.
Restricţii
- 1 ≤ N ≤ 200 000
- 1 ≤ di, vi ≤ 1 000 000 000
- Tribunele Aquilla aprobă această problemă.
| # | Punctaj | Restricţii |
|---|---|---|
| 1 | 6 | N ≤ 20 |
| 2 | 13 | N ≤ 2 000 |
| 3 | 7 | N ≤ 200 000 şi di = 1 pentru orice 1 ≤ i ≤ N |
| 4 | 7 | N ≤ 200 000 şi 1 ≤ di ≤ 2 pentru orice 1 ≤ i ≤ N |
| 5 | 14 | N ≤ 200 000 şi 1 ≤ di ≤ 200 pentru orice 1 ≤ i ≤ N |
| 6 | 12 | N ≤ 100 000 şi şirul d este crescător |
| 7 | 22 | N ≤ 100 000 |
| 8 | 19 | Fără alte restricţii |
Exemplu
| aquilla.in | aquilla.out |
|---|---|
| 3 2 3 2 1 10 100 | 211 |
Explicaţie
- (2, 3): Diferenţa indicilor este 3 - 2 = 1. min(d2, d3) = min(3, 2) = 2. Deoarece 1 nu este divizibil cu 2, acest subşir nu este şmecher.
- (1, 3): Diferenţa indicilor este 3 - 1 = 2. min(d1, d3) = min(2, 2) = 2. Deoarece 2 este divizibil cu 2, subşirul este şmecher. Produsul este v1 * v3 = 1 * 100 = 100.
- (1, 2, 3): Deoarece perechile adiacente (1, 2) şi (2, 3) nu respectă condiţia, subşirul nu este şmecher.
Suma produselor tuturor subşirurilor şmechere este: 1 + 10 + 100 + 100 = 211. 211 mod (109 + 7) = 211.
