← 返回题目列表

Codeforces · 1748/B

B. 多样化的子字符串

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

如果非空数字字符串中每个字符出现的次数不超过其中不同字符的数量,则该字符串是多样化的。

例如:

- 字符串“7”是多样化的,因为 7 出现在其中 $$$1$$$ 次,并且其中不同字符的数量为 $$$1$$$;
- 字符串“77”不是多样化的,因为 7 在其中出现 $$$2$$$ 次,并且其中不同字符的数量为 $$$1$$$;
- 字符串“1010”是多样化的,因为 0 和 1 在其中出现 $$$2$$$ 次,并且其中不同字符的数量为 $$$2$$$;
- 字符串“6668”不多样化,因为 6 在其中出现 $$$3$$$ 次,并且其中不同字符的数量为 $$$2$$$。

给定一个字符串 $$$s$$$,长度为 $$$n$$$,仅包含数字 $$$0$$$ 到 $$$9$$$。找出它的 $$$\frac{n(n+1)}{2}$$$ 子串中有多少个是不同的。

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

请注意,如果相同的不同字符串在 $$$s$$$ 中多次出现,则每次出现都应独立计数。例如,“77”中有两个不同的子字符串都等于“7”,因此字符串“77”的答案是$$$2$$$。

输入

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

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

每个测试用例的第二行包含一个长度为 $$$n$$$ 的字符串 $$$s$$$。保证$$$s$$$的所有字符都是从$$$0$$$到$$$9$$$的数字。

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

输出

对于每个测试用例,打印一个整数 - 给定字符串 $$$s$$$ 的不同子字符串的数量。

示例

输入 #1

7
1
7
2
77
4
1010
5
01100
6
399996
5
23456
18
789987887987998798

输出 #1

1
2
10
12
10
15
106

注意

在第一个测试用例中,不同的子字符串是“7”。

在第二个测试用例中,唯一不同的子字符串是“7”,它出现了两次,所以答案是$$$2$$$。

在第三个测试用例中,不同的子字符串是“0”($$$2$$$次)、“01”、“010”、“1”($$$2$$$次)、“10”($$$2$$$次)、“101”和“1010”。

在第四个测试用例中,不同的子字符串是“0”($$$3$$$次)、“01”、“011”、“0110”、“1”($$$2$$$次)、“10”、“100”、“110”和“1100”。

在第五个测试用例中,不同的子字符串是“3”、“39”、“399”、“6”、“9”($$$4$$$ 次)、“96”和“996”。

在第六个测试用例中,“23456”的所有$$$15$$$非空子串都是多样化的。