← 返回题目列表

Codeforces · 2070/E

E. 二进制字符串游戏

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

考虑以下游戏。两个玩家有一个二进制字符串(由字符组成的字符串 0 和/或 1)。玩家轮流进行,第一个玩家先进行第一个回合。在玩家的回合中,他或她必须选择字符串中两个相邻的元素并将它们删除(第一个元素和最后一个元素也被认为是相邻的)。此外,根据谁采取行动,还有其他限制:

  • 如果是第一个玩家的举动, 两者 选择的字符应该是 0;
  • 如果是第二个玩家的举动, 至少一个 所选字符的 应该是 1.

无法做出有效动作的玩家输掉游戏。这也意味着如果字符串当前少于 $$$2$$$ 个字符,则当前玩家输掉游戏。

给你一个长度为$$$n$$$的二进制字符串$$$s$$$。您必须计算其子串的数量,这样,如果在该子串上进行游戏并且两个玩家都做出最佳决策,则第一个玩家获胜。换句话说,计算 $$$(l, r)$$$ 的对数,使得 $$$1 \le l \le r \le n$$$ 并且第一个玩家在字符串 $$$s_l s_{l+1} \dots s_r$$$ 上有获胜策略。

输入

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

第二行包含字符串 $$$s$$$,由 $$$n$$$ 个字符组成。字符串的每个字符都是 0 or 1.

输出

打印一个整数 - 子串的数量,如果在该子串上进行游戏,则第一个玩家获胜。

示例

输入
复制

10
0010010011

输出
复制

12

注意

在第一个示例中,以下子字符串为第一个玩家获胜($$$s[l:r]$$$ 表示 $$$s_l s_{l+1} \dots s_r$$$):

  • $$$s[1:2]$$$;
  • $$$s[1:3]$$$;
  • $$$s[1:7]$$$;
  • $$$s[2:4]$$$;
  • $$$s[2:8]$$$;
  • $$$s[3:5]$$$;
  • $$$s[4:5]$$$;
  • $$$s[4:6]$$$;
  • $$$s[5:7]$$$;
  • $$$s[6:8]$$$;
  • $$$s[7:8]$$$;
  • $$$s[7:9]$$$。