Изменения

Еще раз используем в качестве примера задачу о замощении. Базовая линия теперь будет ломаной: при прохождении через <tex>i</tex>-ю горизонталь сверху вниз, она переходит на предыдущую вертикаль и спускается до низу.

Профилем будет пара <tex>(<p, i)></tex>, в <tex>p</tex> будет информация о <tex>n + 1</tex> маленьком квадратике слева от базовой линии, имеющем с ней общие точки; <tex>i</tex> обозначает номер горизонтали, на которой произошел излом. Квадратики профиля будут нумероваться сверху вниз, так что угловой будет иметь номер <tex>i + 1</tex>. Горизонтали будем нумеровать с нуля, так что <tex>i</tex> пробегает значения от <tex>0</tex> до <tex>n - 1</tex>.

Для двух профилей <tex>pr1 </tex> = (<tex><p1, i1)></tex> и <tex>pr2 = (<p2, i2) ></tex> положим <tex>d[pr1][pr2] = 1 </tex> если и только если:

а)если 1. Eсли <tex>i < n - 1</tex>, то <tex>i1 + 1 = i2</tex>; иначе <tex>i2 = 0</tex>;б)можно так положить доминошку, накрывающую (i + 1)-й квадратик, что после этого в p2 будет храниться в точности информация о соответствующих квадратиках.Проще говоря, доминошку можно класть только двумя способами -- как показано на рисунках (на (i + 1)-й квадратик можно положить не более одной вертикальной и горизонтальной доминошки). То, что потом получается после сдвига вниз излома, и будет новым профилем. Заметим, что если (i + 1)-я клетка занята, то доминошку уже не надо класть, и (p, i) логично отождествить с (p, i + 1) ("i + 1" пишется условно, нужно всегда иметь в виду возможность i = n - 1).

2. Mожно так положить доминошку, накрывающую <tex><i + 1></tex>-й квадратик, что после этого в <tex>p2</tex> будет храниться в точности информация о соответствующих квадратиках.Проще говоря, доминошку можно класть только двумя способами {{---}} как показано на рисунках (на <tex><i + 1></tex>-й квадратик можно положить не более одной вертикальной и горизонтальной доминошки). То, что потом получается после сдвига вниз излома, и будет новым профилем. Заметим, что если <tex><i + 1></tex>-я клетка занята, то доминошку уже не надо класть, и <tex><p, i></tex> логично отождествить с <tex><p, i + 1></tex>("<tex>i + 1</tex>" пишется условно, нужно всегда иметь в виду возможность <tex>i = n - 1</tex>). Легко заметить, что количество профилей увеличилось в <tex>2n </tex> раз (добавилось число от <tex>1 </tex> до <tex>n </tex> и еще один бит). Но зато количество переходов резко сократилось с 2n <tex>2^n</tex> до <tex>2</tex>.