No.1171 Runs in Subsequences
タグ : / 解いたユーザー数 173
作問者 :
opt
/ テスター :
Kiri8128
問題文
英小文字からなる文字列 $S$ が与えられます．
$S$ の長さを $N$ とすると，$S$ の非空な部分列は全部で $2^N-1$ 個あります（$2$ つの部分列が文字列として同じでも，取り出す位置が異なれば区別します）．
$2^N-1$ 個の各部分列について連 (Run) の個数を求め，その総和を $10^9 + 7$ で割った余りを求めてください．
ここで，文字列の連とは，「同一の文字が連続する非空かつ極大な区間」を指します．
例えば，abbbacc の連は a，bbb，a，cc の $4$ つです．
$2$ つの連が文字列として同じでも，位置が異なれば区別することに注意してください．
入力
入力は以下の形式で与えられる:
$S$
- $S$ は英小文字のみからなる文字列
- $1 \leq |S| \leq 2 \times 10^5$
出力
連の個数の総和を $10^9 + 7$ で割った余りを出力せよ． 最後に改行を出力すること．
サンプル
サンプル1
入力
aba
出力
11
aba の非空部分列は a，b，a，ab，aa，ba，aba の $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もしくは右上の雲マークをクリックしてアカウントを作成してください。