Fişierul intrare/ieşire: | restrictii.in, restrictii.out | Sursă | Algoritmiada 2012, Runda Finala |
Autor | Andrei Grigorean | Adăugată de | |
Timp execuţie pe test | 0.15 sec | Limită de memorie | 20480 kbytes |
Scorul tău | N/A | Dificultate | N/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.in | restrictii.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.