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