| Fişierul intrare/ieşire: | subsiruri3.in, subsiruri3.out | Sursă | ONIS 2014, Runda 4 |
| Autor | Tudose Vlad Andrei | Adăugată de |  FMI No Stress •fmins123 |
| Timp execuţie pe test | 4 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Subsiruri 3
Aurel are un sir de N numere intregi x1, x2, …, xN. El vrea sa afle in cate moduri poate alege un subsir xi1, xi2, …, xiT cu proprietatea ca 0 ≤ xij - xij-1 ≤ K pentru j = 2 … T. Ajutati-l pe Aurel sa raspunda la aceasta intrebare.
Date de intrare
Fişierul de intrare subsiruri3.in va contine pe prima linie T, numarul de teste. Fiecare test va avea pe prima sa line doua numere naturale, N si K, avand semnificatia din enunt. Urmatoarea linie contine N numere intregi, separate printr-un spatiu, reprezentand sirul lui Aurel.
Date de ieşire
În fişierul de ieşire subsiruri3.out se vor afisa T linii, pe linia i aflandu-se numarul de subsiruri cu proprietatea din enunt pentru testul i, modulo 666013.
Restricţii
- 1 ≤ T ≤ 5
- 1 ≤ N ≤ 106
- 0 ≤ K ≤ 109
- 0 ≤ xi ≤ 109 pentru i = 1 … N
- Se numeste subsir al sirului X = (x1, x2, …, xN), un sir Y = (xi1, xi2, …, xiT) cu proprietatea 1 ≤ i1 < i2 < … < iT ≤ N
Exemplu
| subsiruri3.in | subsiruri3.out |
|---|---|
| 1 4 2 6 2 8 9 | 7 |
Explicaţie
Cele 7 subsiruri sunt: {6}, {2}, {8}, {9}, {6, 8}, {6, 8, 9}, {8, 9}.
