← 返回题目列表

Codeforces · 1139/A

A. 偶数子串

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

给定一个字符串 $$$s=s_1s_2\dots s_n$$$,长度为 $$$n$$$,其中仅包含数字 $$$1$$$、$$$2$$$、...、$$$9$$$。

$$$s$$$ 的子串 $$$s[l \dots r]$$$ 是字符串 $$$s_l s_{l + 1} s_{l + 2} \ldots s_r$$$。 $$$s$$$ 的子串 $$$s[l \dots r]$$$ 被调用,即使它代表的数字是偶数。

求 $$$s$$$ 的偶数子串的数量。请注意,即使某些子字符串与字符串相同,但具有不同的 $$$l$$$ 和 $$$r$$$,它们也会被视为不同的子字符串。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 65000$$$) — 字符串 $$$s$$$ 的长度。

第二行包含长度为 $$$n$$$ 的字符串 $$$s$$$。字符串 $$$s$$$ 仅包含数字 $$$1$$$、$$$2$$$、...、$$$9$$$。

输出

打印 $$$s$$$ 的偶数子串的数量。

示例

输入 #1

4
1234

输出 #1

6

输入 #2

4
2244

输出 #2

10

注意

在第一个示例中,偶数子串对应的 $$$[l, r]$$$ 对是:

- $$$s[1 \点 2]$$$
- $$$s[2 \点 2]$$$
- $$$s[1 \点 4]$$$
- $$$s[2 \点 4]$$$
- $$$s[3 \点 4]$$$
- $$$s[4 \点 4]$$$

在第二个示例中,$$$s$$$ 的所有 $$$10$$$ 子串都是偶数子串。请注意,虽然子字符串 $$$s[1 \dots 1]$$$ 和 $$$s[2 \dots 2]$$$ 都定义了子字符串“2”,但它们仍然被视为不同的子字符串。