Изменения
→Пример
==='''Реализация'''===
<font color=green>// n, m {{---}} размер таблицы </font>
'''for''' <tex>\mathtt{i} = \mathtt{0}..(\mathtt{1} \verb|<<| \ \mathtt{n}) - \mathtt{1}</tex> '''for''' <tex>\mathtt{j} = \mathtt{0}..(\mathtt{1} \verb|<<| \ \mathtt{n}) - \mathtt{1}</tex>
'''if''' можно перейти из <tex>\mathtt{i}</tex> в <tex>\mathtt{j}</tex> профиль
<tex>\mathtt{d}[\mathtt{i}][\mathtt{j}] = \mathtt{1}</tex>
<tex>\mathtt{a}[\mathtt{0}][\mathtt{0}] = \mathtt{1}</tex> <font color=green>// Так как мы можем начать только с профиля где все клетки 0 </font>
'''for''' <tex>k = \mathtt{1}..\mathtt{m} - \mathtt{1} </tex>
'''for''' <tex>\mathtt{i} = \mathtt{0}..(\mathtt{1} \verb|<<| \ \mathtt{n}) - \mathtt{1}</tex> '''for''' <tex>\mathtt{j} = \mathtt{0}..(\mathtt{1} \verb|<<| \ \mathtt{n}) - \mathtt{1}</tex>
<tex>\mathtt{a}[\mathtt{k}][\mathtt{i}] = \mathtt{a}[\mathtt{k}][\mathtt{i}] + \mathtt{a}[\mathtt{k} - \mathtt{1}][\mathtt{j}] \cdot \mathtt{d}[\mathtt{j}][\mathtt{i}]</tex>
<tex>\mathtt{ans} = \mathtt{0}</tex>
'''for''' <tex>\mathtt{i} = \mathtt{0}..(\mathtt{1} \verb|<<| lt \lt \ \mathtt{n}) - \mathtt{1}</tex>
'''if''' можно закончить <tex>\mathtt{i}</tex> профилем
<tex>\mathtt{ans} = \mathtt{ans} + \mathtt{a}[\mathtt{m} - \mathtt{1}][\mathtt{i}]</tex>
Тогда <tex>a[k][i]=\displaystyle \sum_{j=0}^{2^n -1} a[k-1][j]\cdot d[j][i]</tex>
Ответом будет <tex> \displaystyle \sum_{ji=0}^{2^n -1} a[m][i]</tex>
==='''Реализация'''===
<font color=green>// n, m {{---}} размер таблицы </font>
'''for''' <tex>\mathtt{i} = \mathtt{0}..(\mathtt{1} \verb|<<| \ \mathtt{n}) - \mathtt{1}</tex> '''for''' <tex>\mathtt{j} = \mathtt{0}..(\mathtt{1} \verb|<<| \ \mathtt{n}) - \mathtt{1}</tex>
'''if''' можно перейти из <tex>\mathtt{i}</tex> в <tex>\mathtt{j}</tex> профиль
<tex>\mathtt{d}[\mathtt{i}][\mathtt{j}]\ =\ \mathtt{1}</tex>
'''else'''
<tex>\mathtt{d}[\mathtt{i}][\mathtt{j}]\ =\ \mathtt{0}</tex>
'''for''' <tex>\mathtt{i} = \mathtt{0}..(\mathtt{1} \verb|<<| \ \mathtt{n}) - \mathtt{1}</tex>
<tex>\mathtt{a}[0][\mathtt{i}]\ = \mathtt{1}</tex> <font color=green >// Так как мы можем начать c любого профиля</font>
'''for''' <tex>\mathtt{k} = \mathtt{1}.. \mathtt{m} - \mathtt{1} </tex>
'''for''' <tex>\mathtt{i} = \mathtt{0}..(\mathtt{1} \verb|<<| \ \mathtt{n}) - \mathtt{1}</tex> '''for''' <tex>\mathtt{j} = \mathtt{0}..(\mathtt{1} \verb|<<| \ \mathtt{n}) - \mathtt{1}</tex>
<tex>\mathtt{a}[\mathtt{k}][\mathtt{i}] = \mathtt{a}[\mathtt{k}][\mathtt{i}] + \mathtt{a}[\mathtt{k} - 1][\mathtt{j}] \cdot \mathtt{d}[\mathtt{j}][\mathtt{i}]</tex>
<tex>\mathtt{ans} = \mathtt{0}</tex>
'''for''' <tex>\mathtt{i} = \mathtt{0}..(\mathtt{1} \verb|<<| \ \mathtt{n}) - \mathtt{1}</tex>
<tex>\mathtt{ans} = \mathtt{ans} + \mathtt{a}[\mathtt{m} - \mathtt{1}][\mathtt{i}]</tex> <font color=green>// Так как мы можем закончить любым профилем </font>
'''return''' <tex>\mathtt{ans}</tex>
=== Пример ===
Еще раз используем в качестве примера задачу о замощении. Базовая линия теперь будет ломаной: при прохождении через <tex>i</tex>-ю горизонталь вертикаль сверху вниз, она переходит на предыдущую вертикаль и спускается до низу. Теперь профиль — это не только маска, но ещё и место излома.
[[Файл:img34.gif|300px|thumb|right|]]
Профилем будет пара <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>d[ipr_1][jpr_2] = 1</tex> если из профиля <tex>pr_1</tex> = <tex>(p_1, i_1)</tex> можно перейти в <tex>pr_2 = (p_2, i_2)</tex>, иначе <tex>0</tex>.
* Eсли <tex>i < n - 1</tex>, то <tex>i_1 + 1 = i_2</tex>, иначе <tex>i_2 = 0 </tex>;
'''if''' <tex>\mathtt{bit}(\mathtt{p, \mathtt{i} + \mathtt{1}}) == \mathtt{0}</tex>
'''if''' <tex>\mathtt{i} == \mathtt{n} - \mathtt{1}</tex>
'''println'''<tex>((\mathtt{p} - (\mathtt{2} \verb|<<| \ \mathtt{i})) \verb|<<| \ \mathtt{1}</tex>, " ", <tex>\mathtt{0})</tex>
'''else'''
'''println'''<tex>(\mathtt{p} - (\mathtt{2} \verb|<<| \ \mathtt{i})</tex>, " ", <tex>\mathtt{i} + \mathtt{1})</tex>
'''else'''
'''if''' <tex>\mathtt{bit}(\mathtt{p}, \mathtt{i}) == \mathtt{0}</tex>
'''if''' <tex>\mathtt{i} == \mathtt{n} - \mathtt{1} </tex>
'''println'''<tex>((\mathtt{p} \verb|<<| \ \mathtt{1})</tex>, " ", <tex>\mathtt{0})</tex>
'''else'''
'''println'''<tex>(\mathtt{p} + (\mathtt{1} \verb|<<| \ \mathtt{n})</tex>, " ", <tex>(\mathtt{i} + \mathtt{1}) % \mathtt{n})</tex>
'''if''' <tex>\mathtt{i} < \mathtt{n} - \mathtt{1}</tex> && <tex>\mathtt{bit}(\mathtt{p, \mathtt{i} + \mathtt{2}}) == \mathtt{0}</tex>
'''println'''<tex>(\mathtt{p} + (\mathtt{4} \verb|<<| \ \mathtt{i})</tex>, " ", <tex>\mathtt{i} + \mathtt{1})</tex>
[[Файл:ok.jpg|640px|thumb|left|Возможные переходы]]
