No.1845 Long Substrings
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.
That is, the string $T$ has length $\sum_{i=1}^{N}A_i$, and the following holds for every $i$:
- The $(1+\sum_{k=1}^{i-1}A_k)$-th through $(\sum_{k=1}^{i}A_k)$-th characters are the same as the $i$-th character of $S$.
Find the number of distinct strings that can occur as a non-empty subsequence of the string $T$. Since the answer can be very large, output it modulo $(10^9+7)$.
▼What is a subsequence?
A string obtained from a given string by removing 0 or more of its characters and arranging the remaining characters in their original order.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
- For $1 \leq i\leq N-1$, $S_i\neq S_{i+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
8
$T={}$aabb, and the possible non-empty subsequences of $T$ are the $8$ strings a, aa, aab, aabb, ab, abb, b, bb, so output $8$.
Sample 2
Input
3 1 1 1 ioi
Output
6
$T={}$ioi, and the possible non-empty subsequences of $T$ are the $6$ strings i, ii, io, ioi, o, oi, so output $6$.
Sample 3
Input
1 27 k
Output
27
Sample 4
Input
6 1 22 333 4444 55555 666666 potato
Output
606835344
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
tatyam
nok0