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

Algoritmi
1

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).

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

2

Io temo di non poterti aiutare più di tanto ma se ancora non lo conosci tieni 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

3

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