CF1930D1 Sum over all Substrings (Easy Version)

这是该问题的简单版本。两种版本的区别仅在于 $t$ 和 $n$ 的约束条件。只有在两种版本都被解决后，才能进行 hack。 对于一个长度为 $m$ 的二进制模式 $p$ 和一个长度为 $m$ 的二进制字符串 $q$，如果对于每个 $i$（$1 \leq i \leq m$），都存在下标 $l$ 和 $r$，使得： - $1 \leq l \leq i \leq r \leq m$，且 - $p_i$ 是字符串 $q_l q_{l+1} \ldots q_r$ 的众数， 则称 $q$ 是 $p$-good 的。 对于一个模式 $p$，记 $f(p)$ 为长度与 $p$ 相同的 $p$-good 二进制字符串中 $\mathtt{1}$ 的最小可能数量。 给定一个长度为 $n$ 的二进制字符串 $s$。请计算 $$ \sum_{i=1}^{n} \sum_{j=i}^{n} f(s_i s_{i+1} \ldots s_j) $$ 即对 $s$ 的所有 $\frac{n(n+1)}{2}$ 个子串，求 $f$ 的值之和。 注： - $^\dagger$ 二进制“模式”是仅由字符 $\mathtt{0}$ 和 $\mathtt{1}$ 组成的字符串。 - $^\ddagger$ 字符 $c$ 是长度为 $m$ 的字符串 $t$ 的众数，当且仅当 $c$ 在 $t$ 中出现的次数不少于 $\lceil \frac{m}{2} \rceil$。例如，$\mathtt{0}$ 是 $\mathtt{010}$ 的众数，$\mathtt{1}$ 不是 $\mathtt{010}$ 的众数，$\mathtt{0}$ 和 $\mathtt{1}$ 都是 $\mathtt{011010}$ 的众数。

每组测试包含多组测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 500$）——测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 100$）——二进制字符串 $s$ 的长度。 每个测试用例的第二行包含一个长度为 $n$ 的二进制字符串 $s$，仅包含字符 $\mathtt{0}$ 和 $\mathtt{1}$。 保证所有测试用例中 $n^2$ 的和不超过 $10^4$。

对于每个测试用例，输出 $s$ 的所有子串的 $f$ 值之和。

在第一个测试用例中，唯一的 $\mathtt{1}$-good 字符串是 $\mathtt{1}$。因此，$f(\mathtt{1})=1$。 在第二个测试用例中，$f(\mathtt{10})=1$，因为 $\mathtt{01}$ 是 $\mathtt{10}$-good 的，而 $\mathtt{00}$ 不是 $\mathtt{10}$-good 的。因此，答案为 $f(\mathtt{1})+f(\mathtt{10})+f(\mathtt{0}) = 1 + 1 + 0 = 2$。 在第三个测试用例中，对于所有 $1 \leq i \leq j \leq 5$，$f$ 都等于 $0$。因此，答案为 $0$。 由 ChatGPT 4.1 翻译