分数: 400 分
问题陈述
Takahashi 正在分析通信系统的日志。在这个系统中,一个位串 S 长度 N 仅包含
记录 0 和 1 。
Takahashi 希望在此信号日志中找到成对的“几乎相同”的间隔。
的连续子串 S 由一对起始位置表示 l 和结束位置 r,表示 (l, r) (1 \leq l \leq r \leq N)。这是指来自的连续部分 l- 第一个字符 r- 第一个字符 S,其长度为 r - l + 1.
一对两个连续的子串 当且仅当满足以下所有条件时, ((l_1, r_1), (l_2, r_2)) 被称为“几乎相同”对:
- (l_1, r_1) \neq (l_2, r_2)。也就是说, l_1 \neq l_2 or r_1 \neq r_2.
- r_1 - l_1 = r_2 - l_2。也就是说,两个连续的子串具有相等的长度。
- 让 L 是两个连续子串的长度。当比较时 i从开头算起第个字符 (1 \leq i \leq L),正好有 1 位置 i 字符不同的地方(即汉明距离恰好是 1).
对计为 无序。也就是说, ((l_1, r_1), (l_2, r_2)) 和 ((l_2, r_2), (l_1, r_1)) 被视为同一对。
请注意,子字符串是通过其位置对来区分的 (l, r)。即使实际的字符串内容相同,如果 (l_1, r_1) \neq (l_2, r_2),它们被视为不同的子字符串。
找出满足条件的对的数量。
约束
- 1 \leq N \leq 5000
- N 是一个整数。
- S 是一个长度为的字符串 N 仅包含
记录
0和1.
输入
N S
- 第一行包含一个整数 N 表示位串的长度。
- 第二行包含一个字符串 S 长度 N 仅包含
记录
0和1.
输出
将满足条件的无序对的数量作为单个整数输出在一行上。
示例输入 1
3 101
示例输出 1
2
示例输入 2
4 0011
示例输出 2
7
示例输入 3
20 01101001011010010110
示例输出 3
298
示例输入 4
50 01001101011010001001110101100110100101101001101011
示例输出 4
2136
示例输入 5
1 0
示例输出 5
0