Fişierul intrare/ieşire:progresii3.in, progresii3.outSursăInfoarena Cup 2014
AutorAdrian BudauAdăugată defreak93Adrian Budau freak93
Timp execuţie pe test0.9 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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

  • 2 ≤ 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.inprogresii3.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, 4, 5} sunt (1,2), (1,4), (1,5), (2,4), (2,5), (4,5)

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content