問題一覧 > 通常問題

No.1481 Rotation ABC

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 45
作問者 : nok0 / テスター : fairy_lettuce chineristAC 👑 ygussany PCTprobability
2 ProblemId : 5901 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-03-21 18:11:05

問題文

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

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

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

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

制約

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