問題一覧 > 通常問題

No.1171 Runs in Subsequences

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 150
作問者 : optopt / テスター : 👑 Kiri8128Kiri8128
19 ProblemId : 4729 / 出題時の順位表
問題文最終更新日: 2020-10-17 00:10:06

問題文

英小文字からなる文字列 $S$ が与えられます.

$S$ の長さを $N$ とすると,$S$ の非空な部分列は全部で $2^N-1$ 個あります($2$ つの部分列が文字列として同じでも,取り出す位置が異なれば区別します).

$2^N-1$ 個の各部分列について (Run) の個数を求め,その総和を $10^9 + 7$ で割った余りを求めてください.

ここで,文字列の連とは,「同一の文字が連続する非空かつ極大な区間」を指します. 例えば,abbbacc の連は abbbacc の $4$ つです. $2$ つの連が文字列として同じでも,位置が異なれば区別することに注意してください.

入力

入力は以下の形式で与えられる:

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

出力

連の個数の総和を $10^9 + 7$ で割った余りを出力せよ. 最後に改行を出力すること.

サンプル

サンプル1
入力
aba
出力
11

aba の非空部分列は abaabaabaaba の $7$ 個あります.

これらの連の個数の総和は $1+1+1+2+1+2+3 = 11$ です.

サンプル2
入力
zzzzzzz
出力
127

非空部分列は $2^7-1 = 127$ 個あります. 連の個数はどれも $1$ なので,$127$ を出力します.

サンプル3
入力
abcaaabacc
出力
3856
サンプル4
入力
supercalifragilisticexpialidocious
出力
636565047

$10^9+7$ で割った余りを出力してください.

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