Fişierul intrare/ieşire:subsir100.in, subsir100.outSursăAlgoritmiada 2009, Runda Finala
AutorAdrian AirineiAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Subsir100

Andreea a primit de la prietena sa Ioana un sir format din N numere naturale. Deoarece Ioanei ii plac subsirurile interesante, ea a rugat-o pe Andreea sa numere cate subsiruri interesante distincte contine sirul de numere. Un subsir este interesant daca oricare doua numere din subsir sunt diferite intre ele. Pentru ca numarul de subsiruri interesante poate fi mare, Andreea va cere sa aflati doar restul impartirii acestui numar la 1000003.

Date de intrare

Fişierul de intrare subsir100.in contine pe prima linie un numar natural N, avand semnificatia din enunt. Pe urmatoarea linie se afla N numere naturale, separate de cate un singur spatiu reprezentand sirul de numere.

Date de ieşire

În fişierul de ieşire subsir100.out se va afla numarul total de subsiruri interesante, modulo 1000003.

Restricţii

  • 1 ≤ N ≤ 100 000
  • Numere din sir sunt numere naturale mai mici decat 2 000 000 000.
  • Considerand ca sirul dat este A=(a1,a2...aN), se numeste subsir al lui A un sir B=(ai1,ai2...aiK) cu proprietatea 1 ≤ i1 < i2 < ... < iK ≤ N.
  • Doua subsiruri B=(bi1,bi2...biK) si C=(cj1,cj2...cjP) sunt distincte daca K este diferit de P sau exista q astfel incat iq sa fie diferit de jq.

Exemplu

subsir100.insubsir100.out
3
1 1 2
5

Explicaţie

Cele 5 subsiruri interesante sunt marcate ingrosat: 1 1 2, 1 1 2, 1 1 2, 1 1 2 si 1 1 2.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content