← 返回题目列表

Codeforces · 2237/D

D. 钢炼金术士

中文机器翻译题面 查看原题

二进制字符串是仅由字符 $$$0$$$ 和 $$$1$$$ 组成的字符串。两个字符 $$$0$$$ 和 $$$1$$$ 称为相反值。

考虑一个二进制字符串$$$t$$$。令 $$$|t|$$$ 为 $$$t$$$ 的长度。当$$$|t|时\ge 2$$$,对于每个 $$$1 \le i \lt |t|$$$,字符 $$$t_i$$$ 和 $$$t_{i+1}$$$ 是相邻的。

调用二进制字符串 $$$t$$$ 美丽 如果可以通过应用以下操作任意次数(可能为零)将其缩减为长度恰好为 $$$1$$$ 的字符串:

  • 选择两个相等的相邻字符,将它们都删除,然后在其位置插入一个具有相反值的字符。

例如,通过将第一个相邻对 $$$\mathtt{00}$$$ 替换为 $$$\mathtt{1}$$$,字符串 $$$\mathtt{10001}$$$ 可以变为 $$$\mathtt{1101}$$$。然后它可以变成$$$\mathtt{001}$$$,然后是$$$\mathtt{11}$$$,最后是$$$\mathtt{0}$$$。因此,$$$\mathtt{10001}$$$ 很漂亮。

另一方面,$$$\mathtt{111}$$$ 并不漂亮。一次运算后,就变成了$$$\mathtt{01}$$$,之后就不能进行任何运算了。

给你一个二进制字符串$$$s$$$。计算$$$s$$$的非空美丽子串$$$^{\text{*}}$$$的数量。

$$$^{\text{*}}$$$ 字符串 $$$a$$$ 是字符串 $$$b$$$ 的子字符串,如果 $$$a$$$ 可以通过从 $$$b$$$ 删除开头的几个(可能是零个或全部)字符和从末尾删除几个(可能是零个或全部)字符来获得。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$) — $$$s$$$ 的长度。

每个测试用例的第二行包含一个长度为$$$n$$$的二进制字符串$$$s$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^6$$$。

输出

对于每个测试用例,输出一个整数——$$$s$$$ 的漂亮子串的数量。

示例

输入
复制

10
1
0
2
01
5
01001
3
001
6
011110
9
010110110
12
010000101001
16
1010011010010110
20
11110101101101001110
30
000101100011111001111100000010

输出
复制

1
2
10
5
15
30
47
81
139
316

注意

在第一个测试用例中,唯一的非空子字符串是 $$$\mathtt{0}$$$,它已经是长度为 $$$1$$$ 的二进制字符串。因此,它是美丽的。

在第二个测试用例中,漂亮的子字符串是 $$$\mathtt{0}$$$ 和 $$$\mathtt{1}$$$。子字符串 $$$\mathtt{01}$$$ 并不美观,因为它的两个字符不相等,因此无法进行任何操作。

在第三个测试用例中,漂亮的子字符串是:

  • $$$s[1,1]=\mathtt{0}$$$;
  • $$$s[2,2]=\mathtt{1}$$$;
  • $$$s[3,3]=\mathtt{0}$$$;
  • $$$s[4,4]=\mathtt{0}$$$;
  • $$$s[5,5]=\mathtt{1}$$$;
  • $$$s[3,4]=\mathtt{00}$$$,可以变成$$$\mathtt{1}$$$;
  • $$$s[2,4]=\mathtt{100}$$$,可以变成$$$\mathtt{11}$$$,然后是$$$\mathtt{0}$$$;
  • $$$s[3,5]=\mathtt{001}$$$,可以变成$$$\mathtt{11}$$$,然后是$$$\mathtt{0}$$$;
  • $$$s[1,4]=\mathtt{0100}$$$,可以变成$$$\mathtt{011}$$$,然后是$$$\mathtt{00}$$$,然后是$$$\mathtt{1}$$$;
  • $$$s[1,5]=\mathtt{01001}$$$,可以变成 $$$\mathtt{0111}$$$,然后是 $$$\mathtt{001}$$$,然后是 $$$\mathtt{11}$$$,最后是 $$$\mathtt{0}$$$。

因此,有 $$$10$$$ 个漂亮的子串。