分数: 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