← 返回题目列表

AtCoder · abc308_e

H. 墨西哥

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

分数: 475 点

问题陈述

给你一个长度-N 序列 A=(A_1,A_2,\dots,A_N) 组成 0, 1,和 2, 和一个长度-N 字符串 S=S_1S_2\dots S_N 组成 M, E,和 X.

求总和 \text{mex}(A_i,A_j,A_k) 所有整数元组 (i,j,k) 这样 1 \leq i < j < k \leq N 和 S_iS_jS_k= MEX。 在这里, \text{mex}(A_i,A_j,A_k) 表示不等于任何一个的最小非负整数 A_i,A_j,也不 A_k.

约束

  • 3\leq N \leq 2\times 10^5
  • N 是一个整数。
  • A_i \in \lbrace 0,1,2\rbrace
  • S 是一个长度为 N 组成 M, E,和 X.

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \dots A_N
S

输出

将答案打印为整数。


示例输入 1

4
1 1 0 2
MEEX

示例输出 1

3

元组 (i,j,k)\ (1 \leq i < j < k \leq N) 这样 S_iS_jS_k = MEX 是以下两个: (i,j,k)=(1,2,4),(1,3,4)。 自从 \text{mex}(A_1,A_2,A_4)=\text{mex}(1,1,2)=0 和 \text{mex}(A_1,A_3,A_4)=\text{mex}(1,0,2)=3,答案是 0+3=3.


示例输入 2

3
0 0 0
XXX

示例输出 2

0

示例输入 3

15
1 1 2 0 0 2 0 2 0 0 0 0 0 2 2
EXMMXXXEMEXEXMM

示例输出 3

13