← 返回题目列表

Codeforces · 1428/F

F. 水果序列

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

动物园管理员正在买一盒水果来喂他的宠物兔子。水果是苹果和橙子的序列,由长度为 $$$n$$$ 的二进制字符串 $$$s_1s_2\ldots s_n$$$ 表示。 $$$1$$$ 代表苹果,$$$0$$$ 代表橙子。

由于 wabbit 对吃橙子过敏,Zookeeper 希望找到最长的连续苹果序列。令 $$$f(l,r)$$$ 为子串 $$$s_{l}s_{l+1}\ldots s_{r}$$$ 中最长的连续苹果序列。

帮助 Zookeeper 找到 $$$\sum_{l=1}^{n} \sum_{r=l}^{n} f(l,r)$$$,或所有子字符串中 $$$f$$$ 的总和。

输入

第一行包含一个整数 $$$n$$$ $$$(1 \leq n \leq 5 \cdot 10^5)$$$。

下一行包含长度为 $$$n$$$ 的二进制字符串 $$$s$$$ $$$(s_i \in \{0,1\})$$$

输出

打印单个整数:$$$\sum_{l=1}^{n} \sum_{r=l}^{n} f(l,r)$$$。

示例

输入 #1

4
0110

输出 #1

12

输入 #2

7
1101001

输出 #2

30

输入 #3

12
011100011100

输出 #3

156

注意

在第一个测试中,有十个子字符串。它们的列表(我们让 $$$[l,r]$$$ 为子字符串 $$$s_l s_{l+1} \ldots s_r$$$):

- $$$[1,1]$$$: 0
- $$$[1,2]$$$: 01
- $$$[1,3]$$$: 011
- $$$[1,4]$$$: 0110
- $$$[2,2]$$$: 1
- $$$[2,3]$$$: 11
- $$$[2,4]$$$: 110
- $$$[3,3]$$$: 1
- $$$[3,4]$$$: 10
- $$$[4,4]$$$: 0

这十个子串中每一个的最长连续序列的长度分别为$$$0,1,2,2,1,2,2,1,1,0$$$。因此,答案是$$$0+1+2+2+1+2+2+1+1+0 = 12$$$。