問題一覧 > 通常問題

No.3458 Scores of Subsequence

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 58
作問者 : くらげ / テスター : tyawanmusi dyktr_06 おのせ hikikomori
ProblemId : 13009 / MMA Contest 021 (順位表) / 自分の提出
問題文最終更新日: 2026-02-27 23:40:00
MMA Contest 021の他の問題:

問題文

文字列 $T$ に対して、スコア $f(T)$ を次のように定めます。

  • ある非負整数 $N$ について、$T$ が $N$ 個の M と $1$ 個の A をこの順に連結してできるとき、$f(T) = 2^N$
  • そうでないとき、$f(T) = 0$

例えば、MMA は $2$ 個の M と $1$ 個の A をこの順に連結したものなので、スコア $f($ MMA $)$ は $4$ です。

M と A のみからなる文字列 $S$ が与えられるので、$S$ の部分列すべてについてスコアを求め、それを合計したものを $998244353$ で割ったあまりを求めてください。

ただし、部分列とは元の文字列から $0$ 文字以上を取り除き、残った文字をもとの順序で連結して得られる文字列を指します。

制約

  • $1 \le |S| \le 2 \times 10^5$
  • $S$ は M と A のみからなる文字列

入力

$S$

出力

$S$ のすべての部分列のスコアの合計を $998244353$ で割ったあまりを $1$ 行で出力してください。

サンプル

サンプル1
入力
MA
出力
3

MA の部分列はM、A、MAの $3$ つであり、スコアはそれぞれ $0$、$1$、$2$ なので $0+1+2=3$ より $3$ が答えになります。

サンプル2
入力
MMMAMMA
出力
270

$S = $ MMMAMMA の部分列のうちスコアが $1$ 以上になるものには A、MMA、MMMMA などがあり、$f($A$) = 1$、$f($MMA$) = 4$、$f($MMMMA$) = 16$ です。

サンプル3
入力
MAMMMAMAMMMMMAMMMMMMMMAMMAMMMA
出力
189496499

答えを $998244353$ で割ったあまりを出力することに注意してください。

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