kdist


Timp maxim de execuţie/test:
0.1 secunde
Memorie totala disponibilă/stivă:
16MB/1 MB

Se dă un şir de N numere naturale din intervalul [1, N] şi un număr natural K.

Cerinţă

Să se determine câte subşiruri cu cel mult K elemente distincte există în şirul dat.

Date de intrare

Fişierul de intrare kdist.in va conţine pe prima linie numere naturale N şi K separate printr-un spaţiu. Pe a doua linie se află N numere naturale separate prin spaţii, reprezentând elementele şirului.

Date de ieşire

Fişierul de ieşire kdist.out va conţine o singură linie pe care se află numărul de subşiruri ale şirului dat care au cel mult K elemente distincte. Rezultatul va fi afişat  modulo 30007.

Restricţii

  • 1 ≤ N ≤ 1000
  • 1 ≤ K ≤ N
  • Pentru 20% din teste N ≤ 15
  • Un subşir conţine cel puţin un element.

Exemplu

kdist.in kdist.out Explicaţie
4 2
1 2 2 3
 12

Cele 12 subşiruri cu cel mult 2 elemente distincte sunt:
1
2
2
3
1 2
1 2
1 3
2 2
2 3
2 3
1 2 2
2 2 3

stud. Mircea Dima
Universitatea Bucureşti
blasterzm@gmail.com