こちらも解法はすぐ思いついたな。
https://yukicoder.me/problems/no/1848
問題
アルファベット小文字で構成されるとても長い文字列が、RLE形式で文字S[i]がA[i]個連続する、という形で与えられる。
Sの(不連続でもよい)部分列としてありうる文字列は、重複を除いて何通りか。
この文字をTとする。
f(i)を、TとTのi文字目以降のprefixの一致文字数とする。
sum(f(i))を答えよ。
解法
共通部分が1種類の文字S[0]だけとなるケースはまず数え上げよう。
それ以外、すなわちS[0]=S[j-1]、S[1]=S[j]となるケースを数え上げることを考える。
まずL[0]≦L[j-1]でなければならず、そのあとS[1+x]=S[j+x]かつL[1+x]=L[j+x]である部分はすべて一致して、その後S[1+y]=S[j+y]かつL[1+y]!=L[j+y]であるyがあったとき、その部分はmin(L[1+y],L[j+y])文字だけ一致することになる。
「S[1+x]=S[j+x]かつL[1+x]=L[j+x]である部分が一致する」ようなxは、(S[i],L[i])の対を並べた配列にZ-algorithmを適用して求めることができる。
vector<int> Zalgo(vector<ll> s) { vector<int> v(1,s.size()); for(int i=1,l=-1,r=-1;i<s.size();i++) { if(i<=r && v[i-l]<r-i+1) v.push_back(v[i-l]); else { l=i; r=(i>r)?i:(r+1); while(r<s.size() && s[r-i]==s[r]) r++; v.push_back((r--)-l); } } v.push_back(0); return v; } int N; ll A[202020],B[202020]; string S; const ll mo=1000000007; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) { cin>>A[i]; if(i) B[i]=B[i-1]+A[i]; } cin>>S; vector<ll> W; for(i=1;i<N;i++) W.push_back(100LL*A[i]+S[i]-'a'); auto V=Zalgo(W); ll ret=0; FOR(i,N) if(S[i]==S[0]) { int nex=1; if(i==N-1||S[1]!=S[i+1]) nex=0; if(A[i]<A[0]) { ret+=A[i]*(A[i]+1)/2%mo; } else { ret+=A[0]*(A[0]+1)/2%mo; ret+=(A[i]-A[0])*A[0]%mo; if(nex) ret+=mo-A[0]; } } for(i=1;i<N;i++) if(S[i]==S[1]&&S[i-1]==S[0]) { if(A[i-1]<A[0]) continue; ret+=A[0]+B[V[i-1]]%mo; if(i+V[i-1]<N&&S[1+V[i-1]]==S[i+V[i-1]]) ret+=min(A[1+V[i-1]],A[i+V[i-1]]); } cout<<ret%mo<<endl; }
まとめ
お疲れさまでした。