分数: 425 点
问题陈述
这个问题是问题G的子问题。
非空字符串 S 组成 0 和 1 满足以下条件时称为漂亮字符串:
- (条件)您可以执行以下操作序列,直到长度达到 S 变为 1 并使唯一剩余的字符 S be
1.- 选择任何整数 i 满意 1 \leq i \leq |S| - 1.
- 定义一个整数 x 如下:
- If S_i =
0和 S_{i+1} =0,让 x = 1. - If S_i =
0和 S_{i+1} =1,让 x = 0. - If S_i =
1和 S_{i+1} =0,让 x = 0. - If S_i =
1和 S_{i+1} =1,让 x = 1.
- If S_i =
- 删除 S_i 和 S_{i+1},并插入对应的数字 x 代替他们的位置。
例如,如果 S=10101然后你选择 i=2,运算后的字符串为1001.
给你一个字符串 T 长度 N 组成 0 和 1.
找出作为子串的漂亮字符串的数量 T。即使两个子字符串与字符串相同,如果它们取自不同的位置,也要单独计数。
什么是子字符串?
A 子字符串 长度为 $$$l$$$ 的字符串 $$$s_1s_2 \ldots s_l$$$ 的 of S 是从开头删除零个或多个字符,从结尾删除零个或多个字符得到的字符串 S.例如,
10 是一个子串 101,但是 11 不是以下的子串 101.
约束
- 1 \leq N \leq 2 \times 10^5
- N 是一个整数。
- T 是一个长度为的字符串 N 组成
0和1.
输入
输入由标准输入按以下格式给出:
N T
输出
打印作为 的子串的漂亮字符串的数量 T.
示例输入 1
3 110
示例输出 1
3
字符串 11 通过取第 1 到第 2 个字符获得 T 是一个漂亮的字符串,因为如果你选择 i=1 并执行运算,字符串变为 1。
美丽的字符串是子字符串 T 是以下三个字符串:
- 字符串
1通过取第一个字符获得 T. - 字符串
1通过取第二个字符获得 T. - 字符串
11通过取第 1 到第 2 个字符获得 T.
示例输入 2
4 0000
示例输出 2
4
示例输入 3
30 011011100101110111100010011010
示例输出 3
225