Изменения
→Решение
==='''Решение'''===
Для удобства можно хранить профиля в виде двоичных масок.
В качестве состояния динамики будем использовать профили размера <tex>n</tex>. В этом профиле <tex>1 </tex> будет означать что клетка закрашена в черный цвет, и <tex>0 </tex> если в белый.
Из профиля <tex>i</tex> в <tex>j</tex>-ый можно перейти если выполнено условие:
* если поставить <tex>i</tex> и <tex>j</tex> профиль рядом, то не должно быть квадратов <tex>2\times 2</tex> одного цвета
Пусть <tex>d[i][j] = 1</tex> если из профиля <tex>i</tex> можно перейти в <tex>j</tex>-ый, иначе <tex>0</tex>.
Пусть так же <tex>a[k][i]</tex> {{- --}} количество способов раскрашивания первые <tex>k-1</tex> столбцов и заканчивавшийся на <tex>i</tex>-ом профиле.
Тогда <tex>a[k][i]=\displaystyle \sum_{j=0}^{2^n -1} a[k-1][j]\cdot d[j][i]</tex>
