C++11(clang++ 3.9) 解法, 执行用时: 2017ms, 内存消耗: 743972K, 提交时间: 2020-10-10 08:05:02

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mo 998244353
#define N 4000010
int t[N][26],ff[N],len[N],la,ct,n,p[N],le[N],f[N],ans,id[N],vt[N],rv[N];
char *s[N],te[N];
vector<int>g[N];
void init(){
	for(int i=1;i<=ct;i++){
		memset(t[i],0,sizeof(t[i]));
		ff[i]=len[i]=f[i]=0;
		g[i].clear();
	}
	ct=la=1;
}
int add(int c,int la,int v){
	int cur=++ct,p=la;
	len[cur]=len[la]+1;
	for(;p&&!t[p][c];p=ff[p])
		t[p][c]=cur;
	if(!p)
		ff[cur]=1;
	else{
		int q=t[p][c];
		if(len[p]+1==len[q])
			ff[cur]=q;
		else{
			int cl=++ct;
			len[cl]=len[p]+1;
			memcpy(t[cl],t[q],sizeof(t[q]));
			ff[cl]=ff[q];
			ff[cur]=ff[q]=cl;
			for(;t[p][c]==q;p=ff[p])
				t[p][c]=cl;
		}
	}
	f[cur]=(f[cur]+v)%mo;
	return cur;
}
void gt(){
	for(int i=2;i<=ct;i++)
		g[ff[i]].push_back(i);
}
void dfs(int x,int t){
	for(int y:g[x]){
		dfs(y,t);
		f[x]=(f[x]+f[y])%mo;
	}
	ans=(ans+((t+mo)%mo)*f[x]%mo*f[x]%mo*(len[x]-len[ff[x]]+mo)%mo)%mo;
}
int cp(int x,int y){
	return le[x]<le[y];
}
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&p[i]);
		p[i]=(1-p[i]+mo)%mo;
		id[i]=i;
	}
	for(int i=1;i<=n;i++){
		scanf("%s",te+1);
		le[i]=strlen(te+1);
		s[i]=new char[le[i]+2];
		for(int j=1;j<=le[i];j++)
			s[i][j]=te[j];
		vt[i]=rv[i]=1;
	}
	sort(id+1,id+n+1,cp);
	init();
	for(int i=1;i<=le[id[n]];i++)
		for(int j=n;j;j--){
			int x=id[j];
			if(le[x]<i)
				break;
			vt[x]=add(s[x][i]-'a',vt[x],p[x]);
			rv[x]=add(s[x][le[x]-i+1]-'a',rv[x],(1-p[x]+mo)%mo);
		}
	gt();
	dfs(1,1);
	for(int i=1;i<=n;i++){
		vt[i]=rv[i]=1;
		init();
		for(int j=1;j<=le[i];j++){
			vt[i]=add(s[i][j]-'a',vt[i],p[i]);
			rv[i]=add(s[i][le[i]-j+1]-'a',rv[i],(1-p[i]+mo)%mo);
		}
		gt();
		dfs(1,-1);
	}
	for(int i=1;i<=n;i++){
		init();
		vt[i]=1;
		for(int j=1;j<=le[i];j++)
			vt[i]=add(s[i][j]-'a',vt[i],1);
		gt();
		dfs(1,1);
	}
	printf("%lld\n",ans);
}