Ссылка на задачу.
Какими могут быть МЕХ-последовательности?
. Тогда если
, то
. Тогда МЕХ-последовательности могут быть либо (0,0,0,..., 0, 1,1,...,1, ..., x - 1, x - 1, x - 1 ,..., x - 1, x,x,...,x) либо (0,0,0,..., 0, 1,1,...,1, ..., x - 1, x - 1, x - 1 ,..., x - 1, x + 1,x + 1,...,x + 1).
Давайте считать динамическое программирование 
количество MEX-С подпоследовательностей первого типа на префиксе длины i с MEX равным j и аналогично
MEX - подпоследовательностей второго типа на префиксе длины i с MEX равным j.
Пусть x текущий элемент последовательности.
В позициях где x < j - 1 или x > j + 1 ничего не меняется.
x = j - 1.