No.2720 Sum of Subarray of Subsequence of...
タグ : / 解いたユーザー数 15
作問者 :
akakimidori
👑
hamamu
Problem Statement
You are given a sequence $A = (A_1, A_2, \ldots, A_N)$ of length $N$ and a string $S$ of length $M$ consisting only of a and s. Let $S_i$ denote the $i$-th character from the left of $S$.
Define functions $f_0, \ldots, f_M$, each of which takes a sequence and returns an integer, as follows:
- For a sequence $B$, $f_0(B)$ is the sum of the elements of $B$.
- For $i$ satisfying $1 \leq i \leq M$ and a sequence $B$,
- if $S_i=$
a, $f_i(B)$ is the sum of $f_{i-1}(C)$ over all non-empty contiguous subarrays $C$ of $B$; - if $S_i=$
s, $f_i(B)$ is the sum of $f_{i-1}(C)$ over all non-empty (not necessarily contiguous) subsequences $C$ of $B$.
- if $S_i=$
Find $f_M(A)$. Since the answer can be very large, print the answer modulo $998244353$.
Here, for both subsequences and contiguous subarrays, two that are equal as sequences are distinguished if the sets of indices of the chosen elements differ.
Constraints
- $1 \leq N \leq 10^5$
- $1 \leq M \leq 10^5$
- $0 \leq A_i < 998244353$
- $S$ is a string of length $M$ consisting only of
aands - All input numbers are integers
Input
The input is given from Standard Input in the following format:
$N \ M$ $A_1 \ \ldots \ A_N$ $S$
Output
Print the answer modulo $998244353$. Print a newline at the end.
Sample
Sample 1
Input
3 2 1 2 3 as
Output
50
Since $S_2=$ s, $f_2(A)$ is the sum of $f_1(B)$ over all non-empty subsequences $B$ of $A$, so
$$
f_2(A) = f_1((1, 2, 3)) + f_1((1, 2)) + f_1((1, 3)) + f_1((2, 3)) + f_1((1)) + f_1((2)) + f_1((3))
$$
holds. Since $S_1=$ a, $f_1(B)$ is the sum of $f_0(C) = (C \text{'s sum of elements})$ over all non-empty contiguous subarrays $C$ of $B$, and the value of each term is computed as follows:
- $f_1((1, 2, 3)) = f_0((1, 2, 3)) + f_0((1, 2)) + f_0((2, 3)) + f_0((1)) + f_0((2)) + f_0((3)) = 6 + 3 + 5 + 1 + 2 + 3 = 20$
- $f_1((1, 2)) = f_0((1, 2)) + f_0((1)) + f_0((2)) = 3 + 1 + 2 = 6$
- $f_1((1, 3)) = f_0((1, 3)) + f_0((1)) + f_0((3)) = 4 + 1 + 3 = 8$
- $f_1((2, 3)) = f_0((2, 3)) + f_0((2)) + f_0((3)) = 5 + 2 + 3 = 10$
- $f_1((1)) = f_0((1)) = 1$
- $f_1((2)) = f_0((2)) = 2$
- $f_1((3)) = f_0((3)) = 3$
Therefore, $$ f_2(A) = 20 + 6 + 8 + 10 + 1 + 2 + 3 = 50 $$ is obtained.
Sample 2
Input
10 7 3 1 4 1 5 9 2 6 5 3 assasas
Output
671269716
Print the answer modulo $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。