問題一覧 > 通常問題

No.1848 Long Prefixes

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 29
作問者 : 👑 potato167potato167 / テスター : 👑 tatyamtatyam
2 ProblemId : 7436 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-02-19 15:46:26

問題文

整数 $N$ 、長さ $N$ の整数列 $A$ 、英小文字からなる長さ $N$ の文字列 $S$ が与えられます。

文字列 $T$ は空文字列から始まって、 $i=1,2,...,N$ の順に、末尾に $S$ の $i$ 文字目を $A_{i}$ 回加えたものです。

つまり、文字列 $T$ は長さ $\sum_{i=1}^{N}A_i$ の文字列で、任意の $i$ に対して以下が成り立ちます。

  • $(1+\sum_{k=1}^{i-1}A_k)$ 文字目から $(\sum_{k=1}^{i}A_k)$ 文字目は $S$ の $i$ 文字目と同じである。

ここで、文字列 $T$ に対して $T_i$ を $T$ の $i$ 文字目以降からなる文字列とし、 $f(i)$ を $T$ と $T_i$ を先頭から見て一致している文字数 (最長共通接頭辞の長さ) とします。

$\sum_{i=1}^{|T|}f(i)$ を $(10^{9}+7)$ で割ったあまりを求めてください。

制約

  • $1\leq N \leq 2\times 10^5$
  • $1\leq A_{i} \leq 10^{9}\ (1\leq i \leq N)$
  • $N$ 及び $A$ の要素は全て整数
  • $S$ は英小文字のみからなる長さ $N$ の文字列
  • $1 \leq i\leq N-1$において、$S_i\neq S_{i+1}$

入力

$N$
$ A_1 \; A_2 \; ...\;A_N$
$S$

出力

答えを $(10^{9}+7)$ で割ったあまりを出力してください。 最後に改行してください。

サンプル

サンプル1
入力
2
2 2
ab
出力
5

$T={}$aabbであり,

$T_{1}={}$aabb, $T_{2}={}$abb, $T_{3}={}$bb, $T_{4}={}$b より、答えは $4+1+0+0=5$ となる。

サンプル2
入力
1
27
k
出力
378
サンプル3
入力
6
1 22 333 4444 55555 666666
tomato
出力
782598

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。