197 Nice Patterns Strike Back

[•peanutz]

Iau TLE pe testul 54. Imi da cineva o idee mai buna decat a mea? Calculez o matrice conf[ x ][ y ][ pow ], sa am configuratii de lungime pow, care sa aiba prima linie conf binara x, si ultima line conf binara y(nu tin ultima dimensiune efectiv, pentru ca nu am nevoie). Si iau fiecare bit din n si determin solutia.

[•wefgef]

Poti construi o dinamica C[ i ][conf] = numarul de configuratii valide de lungime i, astfel incat ultima coloana pusa sa se poate afla din configuratia binara a lui conf. Observam ca pentru a calcula valorile C[ i ][...] avem nevoie doar de valorile C[ i-1 ][...]. Poti sa iti construesti o matrice de 32*32, si sa o ridici la puterea N in timp logartimic.