355
правок
Изменения
→Идемпотентность
$a_l \circ a_{l+1} \circ \dots \circ a_r = (a_l \circ a_{l+1} \circ \dots \circ a_k) \circ (a_{r - k} \circ a_{r - k + 1} \circ \dots \circ a_r)$, где $l \leqslant k \leqslant r$.
|proof=
Покажем, что $a \circ b \circ c \circ d = (a \circ b \circ c) \circ (b \circ c \circ d)$. Действительно, $a \circ b \circ c \circ b \circ c \circ d = a \circ b \circ b \circ c \circ c \circ d = a \circ b \circ c \circ d $. Будем применять это к выражению в правой части равенства до тех пор, пока не получим выражение в левой части. Поле каждого шага количество одинаковых элементов сократится на два. А так как их конечное четное (по $2k - r$ в каждой скобке) число, то и количество шагов будет конечным.
}}
Таким образом мы получаем целый класс задач, которые могут решаться разреженной таблицей.
