Fie A o matrice binara cu R linii si C coloane, numerotate de la 1. Celula din randul i si coloana j contine valoarea 1 daca si numai daca numarul C*(i-1)+j se divide cu p sau cu q, altfel contine valoarea 0.
Vrem sa plasam un singur domino, piesa de marime 1x2 sau 2x1, in matrice. Domino-ul trebuie sa acopere doua celule vecine, pe orizontala sau pe verticala, avand ambele valoarea 0. In cate feluri se poate face acest lucru?
- Date de intrare
- Se citesc pe o singura linie, separate prin spatiu, numerele naturale R, C, p si q.
- Date de iesire
- Se afiseaza un singur numar natural, numarul de plasari valide.
- Restrictii
- 1 <= R, C <= 300 2 <= p, q <= 50
Exemple
Exemplul 1
Intrare
50 50 7 13
Iesire
2959
Exemplul 2
Intrare
10 10 2 3
Iesire
15