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