这是问题的简单版本。两个版本之间的唯一区别是对 $$$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$$$ 是字符串 $$$q_l q_{l+1} \ldots q_{r}$$$ 的模式$$$^\ddagger$$$。
对于模式 $$$p$$$,令 $$$f(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{1}$$$ 的众数$$$\mathtt{011010}$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$) - 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 二进制字符串 $$$s$$$ 的长度。
每个测试用例的第二行包含一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$,仅由字符 $$$\mathtt{0}$$$ 和 $$$\mathtt{1}$$$ 组成。
保证所有测试用例的$$$n^2$$$总和不超过$$$10^4$$$。
输出
对于每个测试用例,输出 $$$f$$$ 在 $$$s$$$ 的所有子字符串上的值之和。
示例
输入 #1
4 1 1 2 10 5 00000 20 11110110000000111111
输出 #1
1 2 0 346
注意
在第一个测试用例中,唯一的 $$$\mathtt{1}$$$ 好字符串是 $$$\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$$$。