# Problema di tiling rettangolo 8xN con piastrelle 1x1 e 2x1

**URL:** <https://forum.olinfo.it/t/problema-di-tiling-rettangolo-8xn-con-piastrelle-1x1-e-2x1/5441>\
**Category:** Algoritmi\
**Created:** [26 Novembre 2018, 10:49pm UTC](https://forum.olinfo.it/t/problema-di-tiling-rettangolo-8xn-con-piastrelle-1x1-e-2x1/5441 "2018-11-26T22:49:36Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![EnderMark](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/e/3e96dc/32.png) [@EnderMark](https://forum.olinfo.it/u/EnderMark)\
**Post date:** [26 Novembre 2018, 10:49pm UTC](https://forum.olinfo.it/t/problema-di-tiling-rettangolo-8xn-con-piastrelle-1x1-e-2x1/5441/1 "2018-11-26T22:49:36Z")

</div>

Buonasera ragazzi, vi chiedo un aiuto per capire come risolvere il problema C (Macarons) della gara di SWERC del 2017 ([https://swerc.eu/theme/problems/swerc.pdf](https://swerc.eu/theme/problems/swerc.pdf)).

Il problema chiede di calcolare il numero di modi per coprire completamente un rettangolo di dimensione (al massimo) 8xN (N \<= 10^18) usando piastrelle di dimensione 1x1 e 2x1.

Da quanto ho capito lo si può attaccare con l’uso di bitmask, la costruzione di recurrence relations e l’esponenziazione veloce di matrici, ma non saprei esattamente come procedere. Potete darmi una mano?

Grazie mille,  
Marco

---

<div class="post-metadata">

**Author:** ![Main](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/e36b37/32.png) [@Main](https://forum.olinfo.it/u/Main)\
**Post date:** [30 Novembre 2018, 5:22pm UTC](https://forum.olinfo.it/t/problema-di-tiling-rettangolo-8xn-con-piastrelle-1x1-e-2x1/5441/2 "2018-11-30T17:22:14Z")

</div>

Io temo di non poterti aiutare più di tanto ma se ancora non lo conosci tieni [https://cses.fi/book/book.pdf](https://cses.fi/book/book.pdf) ;  
c’è una parte dedicata proprio a questo problema (è un po’ sbrigativa).

Che poi, se non ho capito male, potresti direttamente usare la formula che ti dà a pg 76 ma purtroppo non entra nel dettaglio spiegando perché funzioni

---

<div class="post-metadata">

**Author:** ![EnderMark](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/e/3e96dc/32.png) [@EnderMark](https://forum.olinfo.it/u/EnderMark)\
**Post date:** [2 Dicembre 2018, 6:31pm UTC](https://forum.olinfo.it/t/problema-di-tiling-rettangolo-8xn-con-piastrelle-1x1-e-2x1/5441/3 "2018-12-02T18:31:58Z")

</div>

Grazie, ma purtroppo questo algoritmo non è abbastanza efficiente perché M può valere fino a 10^18