Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | progresii3.in, progresii3.out | Sursă | Infoarena Cup 2014 |
Autor | Adrian Budau | Adăugată de | |
Timp execuţie pe test | 0.45 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Progresii 3
Gigel este indragostit de progresii aritmetice. Toata ziua sta si se gandeste la ele asa ca atunci cand a vazut problema Progresii 2 nu putea fi mai fericit. Putea sa stie exact cate progresii aritmetice poate forma de o anumite lungime N cu numerele de la 1 la V. La scurt timp insa si-a dat seama ca solutia acelei probleme nu ii este utila deloc deoarece el are K numere pe care nu le place, deci ar vrea sa nu le vada in nicio progresie aritmetica. Aceste K numere sunt destul de apropiate, distanta cea mai mare dintre ele fiind de maxim 50.000.
Date fiind V, N si cele K numere trebuie sa-i spuneti lui Gigel cate progresii aritmetice cu ratia pozitiva de marime N se pot forma cu numerele de la 1 la V mai putin cele K date. In schimb el va va oferi 100 de puncte.
Deoarece numarul acesta poate fi cam mare Gigel vrea doar restul impartii acestui numar la 1.000.000.009 (un miliard noua)
Date de intrare
Fişierul de intrare progresii3.in va contine pe prima linie 3 numere naturale V, N si K. Urmatorul rand va contine K numere naturale A1, A2, ..., AK reprezentand cele K numere pe care Gigel nu le place.
Date de ieşire
În fişierul de ieşire progresii3.out trebuie sa se gaseasca un singur numar natural, numarul de progresii aritmetice de marime N care contin numere de la 1 la V mai putin cele K date in fisierul de intrare.
Restricţii
- 1 ≤ V ≤ 1.000.000.000.000 (1012)
- 2 ≤ N ≤ 5000
- 1 ≤ K ≤ 50
- K,N ≤ V
- Pentru 20 de puncte V ≤ 100.000, N ≤ 50, K ≤ 30 si distanta maxima dintre doua din cele K valori este maxim 500
- Pentru inca 20 de puncte V ≤ 10.000.000, 100 ≤ N ≤ 150, K ≤ 30 si distanta maxima dintre doua din cele K valori este maxim 500
- Pentru inca 20 de puncte N, K ≤ 20 si distanta maxima dintre doua din cele K valori este maxim 500
Exemplu
progresii3.in | progresii3.out |
---|---|
5 2 1 3 | 6 |
100 10 4 16 25 49 64 | 308 |
Explicaţie
Pentru primul exemplu cele 6 progresii aritmetice de 2 elemente formate din valorile {1, 2, 3, 4} sunt (1,2), (1,4), (1,5), (2,4), (2,5), (4,5)