原题传送门
题目大意：给定长度为n且全由\(0,1,2\)组成的的序列\(a\)，和一个长度为\(n\)且全由\(M,E,X\)组成的字符串\(S\)。对于所有的\(1≤i<j<k≤n\)，\({S_i,S_j,S_k}=MEX\)
.求出 \(\text{mex}\){\(a_i,a_j,a_k\)} 的和。
其中 \(\text{mex}\){\(x,y,z\)} 表示不出现在\(x,y,z\)当中的最小非负整数。
首先很显然有\(O(n^3)\)的暴力做法，即枚举\(M,E,X\)。显然很劣，考虑优化。首先此题关键点在于\(M,E,X\)这个相对位置。所以考虑记录一些东西来快速计算。
对于相对位置的理解：其实对于一个\(E\),可以与它组合在一起的，或者说可以用到它的，只有它前面的\(M\),同理对于一个\(X\),只有它前面已经匹配好的\(ME\)可以与它组合在一起然后产生贡献。
反复提到的其实就是每个字母的前面的一些东西。
显然，递推可以\(O(n)\)地高效解决这道题。
具体来说，我们在扫一遍的时候记录当前已经匹配了多少东西，即\(f_{i,j}\)表示前\(i\)个字符中已经匹配好了\(M,E,X\)中的前\(j\)位的个数。
但是还得记录它们对应的\(a_i\)的值，这个简单，给\(f\)数组多加一维状压记录就好了。
然后就结束了。
奉上我调了很久的代码。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define il inline
#define re register
il int read(){
re int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*f;
}
const int N=200050;
int n;
string s;
int f[N][5][30];
int a[N];
int ans;
inline void copy(int i){
for(re int j=1;j<=3;j++)
for(re int k=0;k<=25;k++)
f[i][j][k]=f[i-1][j][k];
}
int cnt[3];
int solve(int x){
cnt[0]=cnt[1]=cnt[2]=0;
cnt[x%3]++;
cnt[x/3%3]++;
cnt[x/9%3]++;
if(!cnt[0])return 0;
if(!cnt[1])return 1;
if(!cnt[2])return 2;
return 3;
}
signed main(){
cin>>n;
for(re int i=1;i<=n;i++)a[i]=read();
cin>>s;
s+=' ';
for(re int i=n;i;i--)s[i]=s[i-1];
for(re int i=1;i<=n;i++){
copy(i);
if(s[i]=='M')f[i][1][9*a[i]]++;
if(s[i]=='E'){
f[i][2][3*a[i]]+=f[i][1][0];
f[i][2][9+3*a[i]]+=f[i][1][9];
f[i][2][18+3*a[i]]+=f[i][1][18];
}
if(s[i]=='X'){
for(re int j=0;j<=24;j+=3){
f[i][3][j+a[i]]+=f[i][2][j];
}
}
}
for(re int i=0;i<=24;i++){
ans+=solve(i)*f[n][3][i];
}
printf("%lld",ans);
return 0;
}