Не, в этом году не надо

тупейшая динамика на 4 параметра dp[i][beauty][prev][len] — количество строк длиной i c красотой beauty причем последний символ — prev, а длина хвоста вида 01010101 или 10101010 — len

В смысле я видел и dp на 2 параметра и на 3, но это — самая простая как мне кажется

UPD. кстати как оказалось, параметр prev абсолютно лишний

dp[количество поставленных символов][сколько еще нужно хороших подстрок][первый символ]. Заметим, что на результат влияют блоки из чередующихся символов, и эти блоки разделяются повторяющимся символом, например, 1011101 имеет блоки 101, 1, 101. Тогда, чтобы найти dp[i][j][s], переберем длину блока, который мы ставим, и прибавим соответствующее значение динамики.

Pretty simple dp problem.

Dp with 4 parameters: dp[i][b][prev][len] — number of strings with length i having beauty b, last symbol prev and the length of suffix like 010101010 or 10101010 is len.

There are solutions with 3 and 2 parameters, but the one with 4 parameters is the simpliest

Consider any path. When this path is included in the answer, a set of nodes can no longer be included. This always includes one or more leaves. Hence including each path makes 1 or more leaves ineligible for further inclusion. Hence the number of leaves is an upper bound on the answer. The way to realize this upper bound is to select all the leaves as 1 node paths.