#include #include #include #include #define rep(i,a,b) for(int i=(a);i<(b);i++) #define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--) #define all(x) begin(x),end(x) #define sz(x) (int)(x).size() using namespace std; using namespace atcoder; using ll=long long; using ld=long double; using vll=vector; using vvll=vector; using vi=vector; using vvi=vector; using pll=pair; using pi=pair; // using mint=modint998244353; using mint=modint1000000007; // using mint2=static_modint<2>; // using BoostPoint=boost::polygon::point_data; // using Voronoi=boost::polygon::voronoi_diagram; // using mint=LazyMontgomeryModInt<998244353>; using vm=vector; // using vvm=vector; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin>>N; vll A(N); rep(i,0,N)cin>>A[i]; string S; cin>>S; /** * まず、計算量を無視しましょう * 部分列を固定して考えましょう、例えばT=aabaaabaaの時、abaは(1,3,4),(1,3,5),(5,7,8)...で発生します * 最小辞書順の(1,3,4)に注目しましょう * 実は部分列は、この最小辞書順の添字列と一対一に対応します * dp[i]を最小辞書順の添字列の最後尾がiの時の数として * dp[i] = \sum_{k=j}^{i-1} dp[k] (jはT[j]=T[i]かつj=0&&S[k]!=S[i];--k){ dp[i]+=dp[k]*A[k]; } if(k<0)dp[i]++; else dp[i]+=dp[k]; ans+=dp[i]*A[i]; } cout<