問題一覧 > 通常問題

No.1481 Rotation ABC

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 35
作問者 : nok0nok0 / テスター : 👑 fairy_lettucefairy_lettuce chineristACchineristAC ygussanyygussany PCTprobabilityPCTprobability
2 ProblemId : 5901 / 出題時の順位表
問題文最終更新日: 2021-03-21 18:11:05

問題文

A,B,C からなる長さ $N$ の文字列 $S$ があります。

あなたは $S$ に対して、以下の操作を $0$ 回以上行うことができます。

  • $S_i =$ A, $S_j = $B,$S_k =$ C なる組 $\left(i,j,k\right)$ を選ぶ。$S_i,S_j,S_k$ をそれぞれ B,C,A で置き換える。ただし選択する組 $\left(i,j,k\right)$ に関して、以下のいずれかの大小関係が成立している必要がある。
    • $1 \le i < j < k \le N$
    • $1 \le j < k < i \le N$
    • $1 \le k < i < j \le N$

操作を $0$ 回以上行ったあとの $S$ として、ありうるものの種類数を $998244353$ で割った余りを出力してください。

制約

  • $1\le N \le 10^5$
  • $S$ は A,B,C からなる長さ $N$ の文字列である。

入力

$N$
$S$

出力

操作を $0$ 回以上行ったあとの $S$ として、ありうるものの種類数を $998244353$ で割った余りを出力せよ。

サンプル

サンプル1
入力
3
ABC
出力
3

操作を $0$ 回行うことで ABC が、 $1$ 回行うことで BCA が、$2$ 回行うことで CAB が得られます。

サンプル2
入力
5
AAAAB
出力
1

操作は $1$ 回も行えません。

サンプル3
入力
4
AABC
出力
8

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