311072: CF1930D1. Sum over all Substrings (Easy Version)
Description
This is the easy version of the problem. The only difference between the two versions is the constraint on $t$ and $n$. You can make hacks only if both versions of the problem are solved.
For a binary$^\dagger$ pattern $p$ and a binary string $q$, both of length $m$, $q$ is called $p$-good if for every $i$ ($1 \leq i \leq m$), there exist indices $l$ and $r$ such that:
- $1 \leq l \leq i \leq r \leq m$, and
- $p_i$ is a mode$^\ddagger$ of the string $q_l q_{l+1} \ldots q_{r}$.
For a pattern $p$, let $f(p)$ be the minimum possible number of $\mathtt{1}$s in a $p$-good binary string (of the same length as the pattern).
You are given a binary string $s$ of size $n$. Find $$\sum_{i=1}^{n} \sum_{j=i}^{n} f(s_i s_{i+1} \ldots s_j).$$ In other words, you need to sum the values of $f$ over all $\frac{n(n+1)}{2}$ substrings of $s$.
$^\dagger$ A binary pattern is a string that only consists of characters $\mathtt{0}$ and $\mathtt{1}$.
$^\ddagger$ Character $c$ is a mode of string $t$ of length $m$ if the number of occurrences of $c$ in $t$ is at least $\lceil \frac{m}{2} \rceil$. For example, $\mathtt{0}$ is a mode of $\mathtt{010}$, $\mathtt{1}$ is not a mode of $\mathtt{010}$, and both $\mathtt{0}$ and $\mathtt{1}$ are modes of $\mathtt{011010}$.
InputEach test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer $n$ ($1 \le n \le 100$) — the length of the binary string $s$.
The second line of each test case contains a binary string $s$ of length $n$ consisting of only characters $\mathtt{0}$ and $\mathtt{1}$.
It is guaranteed that the sum of $n^2$ over all test cases does not exceed $10^4$.
OutputFor each test case, output the sum of values of $f$ over all substrings of $s$.
ExampleInput4 1 1 2 10 5 00000 20 11110110000000111111Output
1 2 0 346Note
In the first test case, the only $\mathtt{1}$-good string is $\mathtt{1}$. Thus, $f(\mathtt{1})=1$.
In the second test case, $f(\mathtt{10})=1$ because $\mathtt{01}$ is $\mathtt{10}$-good, and $\mathtt{00}$ is not $\mathtt{10}$-good. Thus, the answer is $f(\mathtt{1})+f(\mathtt{10})+f(\mathtt{0}) = 1 + 1 + 0 = 2$.
In the third test case, $f$ equals to $0$ for all $1 \leq i \leq j \leq 5$. Thus, the answer is $0$.
Output
这是一个关于二进制字符串的题目,分为简单和困难两个版本,两者的区别仅在于限制条件$t$和$n$的不同。只有当两个版本的问题都解决后,才能进行黑客攻击。
对于一个长度为$m$的二进制模式$p$和一个二进制字符串$q$,如果对于任意的$i$($1 \leq i \leq m$),都存在下标$l$和$r$满足以下条件:
1. $1 \leq l \leq i \leq r \leq m$,并且
2. $p_i$是字符串$q_l q_{l+1} \ldots q_{r}$的众数。
那么,称$q$是$p$-好的。对于模式$p$,记$f(p)$为满足上述条件的$p$-好二进制字符串中$\mathtt{1}$的最小可能数量。
给定一个长度为$n$的二进制字符串$s$,需要计算
\[
\sum_{i=1}^{n} \sum_{j=i}^{n} f(s_i s_{i+1} \ldots s_j).
\]
即对所有$\frac{n(n+1)}{2}$个$s$的子字符串求$f$的值并求和。
输入输出数据格式:
输入:
- 第一行包含一个整数$t$($1 \le t \le 500$),表示测试用例的数量。
- 每个测试用例包含两行:
- 第一行包含一个整数$n$($1 \le n \le 100$),表示二进制字符串$s$的长度。
- 第二行包含一个长度为$n$的二进制字符串$s$,只包含字符$\mathtt{0}$和$\mathtt{1}$。
- 保证所有测试用例的$n^2$之和不超过$10^4$。
输出:
- 对于每个测试用例,输出一个整数,表示所有子字符串的$f$值之和。
示例输入输出:
输入:
```
4
1
1
2
10
5
00000
20
11110110000000111111
```
输出:
```
1
2
0
346
```
注意:
- 在第一个测试用例中,唯一的$\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$。
- 在第三个测试用例中,对于所有$1 \leq i \leq j \leq 5$,$f$的值都是$0$。因此,答案是$0$。题目大意: 这是一个关于二进制字符串的题目,分为简单和困难两个版本,两者的区别仅在于限制条件$t$和$n$的不同。只有当两个版本的问题都解决后,才能进行黑客攻击。 对于一个长度为$m$的二进制模式$p$和一个二进制字符串$q$,如果对于任意的$i$($1 \leq i \leq m$),都存在下标$l$和$r$满足以下条件: 1. $1 \leq l \leq i \leq r \leq m$,并且 2. $p_i$是字符串$q_l q_{l+1} \ldots q_{r}$的众数。 那么,称$q$是$p$-好的。对于模式$p$,记$f(p)$为满足上述条件的$p$-好二进制字符串中$\mathtt{1}$的最小可能数量。 给定一个长度为$n$的二进制字符串$s$,需要计算 \[ \sum_{i=1}^{n} \sum_{j=i}^{n} f(s_i s_{i+1} \ldots s_j). \] 即对所有$\frac{n(n+1)}{2}$个$s$的子字符串求$f$的值并求和。 输入输出数据格式: 输入: - 第一行包含一个整数$t$($1 \le t \le 500$),表示测试用例的数量。 - 每个测试用例包含两行: - 第一行包含一个整数$n$($1 \le n \le 100$),表示二进制字符串$s$的长度。 - 第二行包含一个长度为$n$的二进制字符串$s$,只包含字符$\mathtt{0}$和$\mathtt{1}$。 - 保证所有测试用例的$n^2$之和不超过$10^4$。 输出: - 对于每个测试用例,输出一个整数,表示所有子字符串的$f$值之和。 示例输入输出: 输入: ``` 4 1 1 2 10 5 00000 20 11110110000000111111 ``` 输出: ``` 1 2 0 346 ``` 注意: - 在第一个测试用例中,唯一的$\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$。 - 在第三个测试用例中,对于所有$1 \leq i \leq j \leq 5$,$f$的值都是$0$。因此,答案是$0$。