Изменения
→Решение
Для удобства можно хранить профили в виде двоичных масок.
В качестве состояния динамики будем использовать профили размерами <tex>n</tex>. В этом профиле <tex>1 </tex> будет означать, что домино лежит горизонтально и заканчивается на этом столбце, иначе <tex>0</tex>. Таких профилей будет <tex>2^n</tex>.
Теперь проверим из какого профиля в какой можно перейти.
Из профиля <tex>i</tex> в профиль <tex>j</tex> можно перейти если выполняются условия:
* Можно положить горизонтальные домино. То есть там где в <tex>j</tex> профиле стоит <tex>1</tex>, в <tex>i</tex> профиле должен стоять <tex>0</tex>.
* Можно доложить в оставшиеся клетки вертикальные домино. То есть оставшиеся <tex>0 </tex> в <tex>i</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>
Ответом будет <tex> \sum a[m][i]</tex>, где <tex>i</tex> : {{---}} профиль, который может быть последним (т.е. все группы из <tex>0 </tex> имеют четные размеры)
==='''Реализация'''===
