問題一覧 > 通常問題

No.2419 MMA文字列2

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 155
作問者 : dyktr_06dyktr_06 / テスター : 👑 Nafmo2Nafmo2 LaFolia13LaFolia13 hikikomorihikikomori sepa38sepa38 Seed57_cashSeed57_cash UdonUdon ryota2357ryota2357
1 ProblemId : 9701 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-08-12 13:31:36

問題文

MMA 文字列とは、$3$ 文字の文字列で、$2$ 種類のアルファベットからなり、$1$ 文字目と $2$ 文字目が一致しているものを指します。

英大文字のみからなる文字列 $S$ が与えられるので、この文字列 $S$ の連続とは限らない部分列であって、MMA 文字列であるものは何通りあるかを求めてください。

なお、取り出した部分列が列として等しい場合でも、選んだ位置の集合が異なれば別の取り出し方として数えます。

制約

  • $3 \leq | S | \leq 2 \times 10^5$
  • $S$ は英大文字のみからなる文字列

入力

入力は以下の形式で標準入力から与えられる。

$S$

出力

問題の答えを一行に出力せよ。

サンプル

サンプル1
入力
CIRCLEMMA
出力
6

連続するとは限らない部分列であって、MMA文字列であるようなものは以下の $6$ 通りです。

  • $1, 4, 5$ 文字目を取り出したCCL
  • $1, 4, 6$ 文字目を取り出したCCE
  • $1, 4, 7$ 文字目を取り出したCCM
  • $1, 4, 8$ 文字目を取り出したCCM
  • $1, 4, 9$ 文字目を取り出したCCA
  • $7, 8, 9$ 文字目を取り出したMMA

サンプル

サンプル2
入力
MMACONTESTISFORBEGINNERS
出力
82

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