No.1845 Long Substrings
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 80
作問者 : 👑
potato167
/ テスター :
tatyam
nok0
タグ : / 解いたユーザー数 80
作問者 : 👑
potato167
/ テスター :
tatyam
nok0
問題文最終更新日: 2022-01-17 15:40:07
問題文
整数 $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$ の空でない部分列としてありうる文字列は何通りあるか求めてください。 また、答えは非常に大きくなることがあるので、$(10^9+7)$ で割ったあまりを出力してください。
▼部分列とは？
文字列に対して、その文字列を構成する文字を 0 文字以上取り除き、残った文字を元の順番に並べた文字列のこと。制約
- $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
出力
8
$T={}$aabb であり、$T$ の空でない部分列としてあり得るのは、a, aa, aab, aabb, ab, abb, b, bb の $8$ 通りであるので、$8$ を出力します。
サンプル2
入力
3 1 1 1 ioi
出力
6
$T={}$ioi であり、$T$ の空でない部分列としてあり得るのは、i, ii, io, ioi, o, oi の $6$ 通りであるので、$6$ を出力します。
サンプル3
入力
1 27 k
出力
27
サンプル4
入力
6 1 22 333 4444 55555 666666 potato
出力
606835344
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。