問題一覧 > 通常問題

No.2021 Not A but B

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 176
作問者 : milkcoffee / テスター : first_vil
2 ProblemId : 7969 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-07-27 14:39:01

問題文

A, B からなる長さ NN の文字列 SS が与えられます。あなたは以下の操作を SS に対してちょうど 11 回だけ行います。

  • SS の連続する 22 文字を選び、その 22 文字をどちらも B に置き換える。

    • 操作後の文字列 SS としてあり得るのは何通りですか。

    入力

    NN
SS

  • 2≤N≤2×1052 \leq N \leq 2 \times 10^5
  • NN は整数である
  • SS は A, B からなる長さ NN の文字列

    • 出力

    操作後の SS としてあり得る SS の通り数を整数で出力してください。

    サンプル

    サンプル1
    入力
    4
AABA
    出力
    3

    あり得るのは以下の 33 通りです。
    BBBA
    ABBA
    AABB

    サンプル2
    入力
    3
ABB
    出力
    2

    あり得るのは以下の 22 通りです。
    BBB
    ABB

    サンプル3
    入力
    7
ABABABA
    出力
    4

    あり得るのは以下の 44 通りです。
    BBABABA
    ABBBABA
    ABABBBA
    ABABABB

    サンプル4
    入力
    40
ABBAABABAAABABBAABABAAABAAABBABAAAABBABA
    出力
    31

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