Fişierul intrare/ieşire:restrictii.in, restrictii.outSursăAlgoritmiada 2012, Runda Finala
AutorAndrei GrigoreanAdăugată defreak93Adrian Budau freak93
Timp execuţie pe test0.3 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Restrictii

Se da un numar natural VAL, si un sir A, format din N numere naturale, din intervalul [0, VAL - 1]. Asupra sirului A se impun o serie de M restrictii de forma: suma elementelor de pe pozitiile cuprinse intre X si Y (inclusiv X si Y) trebuie sa fie egala cu Z, modulo VAL. Dandu-se VAL, N si cele M restrictii, sa se calculeze numarul de siruri A care respecta toate cele M restrictii, si sa se afiseze modulo 666013.

Date de intrare

Fişierul de intrare restrictii.in va contine pe prima linie numerele N, M si VAL. Urmatoarele M linii vor avea formatul X Y Z, cu semnificatia din enunt.

Date de ieşire

În fişierul de ieşire restrictii.out se va afla pe prima linie raspunsul cautat, modulo 666013.

Restricţii

  • 1 ≤ N ≤ 50.000
  • 1 ≤ M ≤ 100.000
  • 1 ≤ VAL ≤ 1.000.000.000

Exemplu

restrictii.inrestrictii.out
5 5 6
1 5 2
3 4 5
4 5 0
4 4 4
3 5 1
6
3 3 5
1 3 2
1 2 3
3 3 3
0

Explicaţie

Pentru primul exemplu solutiile sunt 1 0 1 4 2, 3 4 1 4 2, 4 3 1 4 2, 2 5 1 4 2, 0 1 1 4 2 si 5 2 1 4 2

Pentru al doilea exemplu nu exista nicio solutie sa satisfaca toate cele 3 restrictii.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content