問題一覧 > 通常問題

No.1927 AB-CD

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 108
作問者 : milkcoffeemilkcoffee / テスター : 遭難者遭難者
3 ProblemId : 7878 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-04-09 12:13:52

問題文

A,B,C,D からなる長さ $N$ の文字列 $S$ が与えられます。あなたは以下の操作を $S$ に対して好きなだけ行うことができます。

  • 連続した異なる $2$ つの文字を選ぶ。ただし、連続する $2$ 文字として AB,BA,CD,DC を選ぶことはできない。そして、選んだ $2$ つの文字を入れ替える。

  • この操作を $0$ 回以上行って得られる文字列 $S$ は何通りあるかを $998244353$ で割った余りを求めてください。

    入力

    $N$
    $S$
    

  • $2 \leq N \leq 3 \times 10^5$
  • $N$ は整数である
  • $S$ は A,B,C,D からなる長さ $N$ の文字列
  • 出力

    操作後に得られる文字列 $S$ として考えられる種類数を $998244353$ で割った余りを整数で出力してください。

    サンプル

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

    操作後の文字列 $S$ として考えられるのは以下の $3$ 通りです。
    ABC, ACB, CAB

    AB を入れ替えられないことに注意してください。

    サンプル2
    入力
    6
    CCDDCC
    
    出力
    1
    

    操作後の $S$ として考えられるのは、CCDDCC の $1$ 通りです。

    サンプル3
    入力
    100
    BDBADDDACABABABDDADBBCBDBBDCBBCAAACCDBBDDAABAACDDAAACBCDABBCADAAABCCCAADBADBBCACADCACADAACBACCBADAAA
    
    出力
    472878571
    

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