問題一覧 > 通常問題

No.1848 Long Prefixes

レベル : / AI推定難易度 : 1950 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 28
作問者 : 👑 potato167 / テスター : tatyam
お気に入りにしたユーザー ProblemId : 7436 / 自分の提出
問題文最終更新日: 2022-02-19 15:46:26
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 332 (順位表) の他の問題:

Problem Statement

You are given an integer $N$, an integer sequence $A$ of length $N$, and a string $S$ of length $N$ consisting of lowercase English letters.

The string $T$ is obtained by starting from the empty string and, in the order $i=1,2,...,N$, appending the $i$-th character of $S$ to the end $A_{i}$ times.

In other words, the string $T$ has length $\sum_{i=1}^{N}A_i$, and the following holds for every $i$.

  • The characters from the $(1+\sum_{k=1}^{i-1}A_k)$-th to the $(\sum_{k=1}^{i}A_k)$-th are the same as the $i$-th character of $S$.

Here, for the string $T$, let $T_i$ be the string consisting of the $i$-th and subsequent characters of $T$, and let $f(i)$ be the number of characters that match between $T$ and $T_i$ when compared from the beginning (the length of their longest common prefix).

Find $\sum_{i=1}^{|T|}f(i)$ modulo $(10^{9}+7)$.

Constraints

  • $1\leq N \leq 2\times 10^5$
  • $1\leq A_{i} \leq 10^{9}\ (1\leq i \leq N)$
  • $N$ and all elements of $A$ are integers
  • $S$ is a string of length $N$ consisting only of lowercase English letters
  • $S_i\neq S_{i+1}$ for $1 \leq i\leq N-1$

Input

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

Output

Output the answer modulo $(10^{9}+7)$. Print a newline at the end.

Sample

Sample 1
Input
2
2 2
ab
Output
5

$T={}$aabb, and

since $T_{1}={}$aabb, $T_{2}={}$abb, $T_{3}={}$bb, $T_{4}={}$b, the answer is $4+1+0+0=5$.

Sample 2
Input
1
27
k
Output
378
Sample 3
Input
6
1 22 333 4444 55555 666666
tomato
Output
782598

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