問題一覧 > 通常問題

No.1927 AB-CD

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 135
作問者 : milkcoffeemilkcoffee / テスター : 遭難者遭難者
4 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

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

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

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

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

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