No.3202 Periodic Alternating Subsequence
タグ : / 解いたユーザー数 48
作問者 :
YY-otter
/ テスター :
👑 
p-adic
問題文
あなたは、ある規則によって生成されるバイナリ列を解析しています。
長さ $|T|$ の文字列 $T$ と、正の整数 $K$ が与えられます。
これらから、長さ $N=|T|\times K$ の文字列 $S$ が、$T$ を $K$ 回順に繋げることによって生成されます。
この文字列 $S$ の部分列(連続である必要はない)であって、同じ文字が連続しないものを「交互部分列」と呼びます。
空でないすべての交互部分列を考えます。それぞれの部分列に対して、その長さの $2$ 乗をスコアとして定義します。
すべての空でない交互部分列のスコアの総和を、$1000000007=10^9+7$ で割った余りを求めてください。
ただし、ある $2$ つの交互部分列が列として同じでも、取り出された位置が異なるならそれらは別々にスコアに数えるものとします。
入力
$T$ $K$
- $1\leq |T| \leq 2\times10^5$
- $T$ は
0と1のみからなる文字列 - $1\leq K\leq 10^{18}$
出力
スコアの総和を、$1000000007=10^9+7$ で割った余りを出力してください。
最後に改行してください。
サンプル
サンプル1
入力
01 2
出力
54
$T=$01$,\ K=2$ なので、対象の文字列 $S$ は 0101 です。
空でない交互部分列とそのスコアは以下の通りです。
- 長さ $1$ :
0( $2$ 通り),1( $2$ 通り) $\rightarrow$ スコア: $1^2\times (2+2)=4$ - 長さ $2$ :
01( $3$ 通り),10( $1$ 通り) $\rightarrow$ スコア: $2^2\times (3+1)=16$ - 長さ $3$ :
010( $1$ 通り),101( $1$ 通り) $\rightarrow$ スコア: $3^2\times (1+1)=18$ - 長さ $4$ :
0101( $1$ 通り) $\rightarrow$ スコア: $4^2\times 1=16$
01が $3$ 通りの作り方があることに注意してください( $1$ 文字目と $2$ 文字目、$1$ 文字目と $4$ 文字目、$3$ 文字目と $4$ 文字目の取り方の $3$ 通り)。
サンプル2
入力
0 1000000000000000000
出力
49
$S$ は0が $10^{18}$ 個並んだ文字列です。
空でない交互部分列は、いずれかの0を $1$ つ選ぶ $10^{18}$ 通りです。
よって、$1^2\times 10^{18}\mod (10^9+7)=49$ を出力します。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。