Это простая версия задачи. Единственное отличие между версиями заключается в ограничениях на \(t\) и \(n\). Вы можете делать взломы только тогда, когда обе версии задачи решены.
Для бинарного\(^\dagger\) шаблона \(p\) и бинарной строки \(q\) одинаковой длины \(m\), скажем, что строка \(q\) называется \(p\)-хорошей, если для каждого \(i\) (\(1 \leq i \leq m\)) существуют индексы \(l\) и \(r\) такие, что:
- \(1 \leq l \leq i \leq r \leq m\), и
- \(p_i\) является модой\(^\ddagger\) строки \(q_l q_{l+1} \ldots q_{r}\).
Для шаблона \(p\) определим \(f(p)\) как минимально возможное количество \(\mathtt{1}\) в \(p\)-хорошей бинарной строке (такой же длины, как и шаблон).
Вам дана бинарная строка \(s\) длины \(n\). Найдите \(\)\sum_{i=1}^{n} \sum_{j=i}^{n} f(s_i s_{i+1} \ldots s_j).\(\) Другими словами, вам нужно просуммировать значения \(f\) по всем \(\frac{n(n+1)}{2}\) подстрокам \(s\).
\(^\dagger\) Бинарный шаблон — это строка, состоящая только из символов \(\mathtt{0}\) и \(\mathtt{1}\).
\(^\ddagger\) Символ \(c\) является модой строки \(t\) длины \(m\), если число вхождений \(c\) в \(t\) не меньше \(\lceil \frac{m}{2} \rceil\). Например, \(\mathtt{0}\) является модой \(\mathtt{010}\), \(\mathtt{1}\) не является модой \(\mathtt{010}\), и оба символа \(\mathtt{0}\) и \(\mathtt{1}\) являются модами \(\mathtt{011010}\).
Примечание
В первом наборе входных данных единственной \(\mathtt{1}\)-хорошей строкой является \(\mathtt{1}\). Таким образом, \(f(\mathtt{1})=1\).
Во втором наборе входных данных \(f(\mathtt{10})=1\), так как \(\mathtt{01}\) является \(\mathtt{10}\)-хорошей, а \(\mathtt{00}\) не является \(\mathtt{10}\)-хорошей. Таким образом, ответ равен \(f(\mathtt{1})+f(\mathtt{10})+f(\mathtt{0}) = 1 + 1 + 0 = 2\).
В третьем наборе входных данных \(f\) равна \(0\) для всех \(1 \leq i \leq j \leq 5\). Таким образом, ответ равен \(0\).