問題一覧 > 通常問題

No.2720 Sum of Subarray of Subsequence of...

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 13
作問者 : ecotteaecottea / テスター : akakimidoriakakimidori hamamuhamamu
6 ProblemId : 10587 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-03-25 19:32:51

問題文

長さ $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)$ の総和とする．

$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もしくは右上の雲マークをクリックしてアカウントを作成してください。