No.2720 Sum of Subarray of Subsequence of...
タグ : / 解いたユーザー数 14
作問者 : ecottea / テスター : akakimidori hamamu
問題文
長さ $N$ の数列 $A = (A_1, A_2, \ldots, A_N)$ と,a
,s
のみからなる長さ $M$ の文字列 $S$ が与えられます.$S$ の左から $i$ 番目の文字を $S_i$ と表します.
与えられた数列に対して整数を返す関数 $f_0, \ldots, f_M$ を以下のように定めます:
- 数列 $B$ に対し,$f_0(B)$ を $B$ の要素の総和とする.
- $1 \leq i \leq M$ を満たす $i$ と数列 $B$ に対し,
- $S_i=$
a
のとき,$f_i(B)$ を $B$ の空でない連続部分列 $C$ 全てをわたる $f_{i-1}(C)$ の総和とする. - $S_i=$
s
のとき,$f_i(B)$ を $B$ の空でない(連続とは限らない)部分列 $C$ 全てをわたる $f_{i-1}(C)$ の総和とする.
- $S_i=$
$f_M(A)$ を求めてください.答えは非常に大きくなることがあるので,答えを $998244353$ で割った余りを出力してください.
ただし部分列,連続部分列ともに,数列として等しい場合でも選んだ要素の添字の集合が異なれば区別します.
制約
- $1 \leq N \leq 10^5$
- $1 \leq M \leq 10^5$
- $0 \leq A_i < 998244353$
- $S$ は
a
,s
のみからなる長さ $M$ の文字列 - 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられます.
$N \ M$ $A_1 \ \ldots \ A_N$ $S$
出力
答えを $998244353$ で割った余りを出力してください. 最後に改行してください.
サンプル
サンプル1
入力
3 2 1 2 3 as
出力
50
$S_2=$ s
なので $f_2(A)$ は $A$ の空でない部分列 $B$ 全てをわたる $f_1(B)$ の総和となり,
$$
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))
$$
です.$S_1=$ a
なので $f_1(B)$ は $B$ の空でない連続部分列 $C$ 全てをわたる $f_0(C) = (C \text{の要素の総和})$ の総和となり,各項の値は
- $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$
と計算できます.以上より $$ f_2(A) = 20 + 6 + 8 + 10 + 1 + 2 + 3 = 50 $$ となります.
サンプル2
入力
10 7 3 1 4 1 5 9 2 6 5 3 assasas
出力
671269716
$998244353$ で割った余りを出力してください.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。