No.3202 Periodic Alternating Subsequence
Problem Statement
You are analyzing a binary string generated by a certain rule.
You are given a string $T$ of length $|T|$ and a positive integer $K$.
From these, a string $S$ of length $N=|T|\times K$ is generated by concatenating $T$ in order $K$ times.
A subsequence of this string $S$ (not necessarily contiguous) in which no two adjacent characters are the same is called an "alternating subsequence".
Consider all non-empty alternating subsequences. For each subsequence, its score is defined as its length raised to the power of $2$.
Find the sum of the scores of all non-empty alternating subsequences, modulo $1000000007=10^9+7$.
Here, even if $2$ alternating subsequences are identical as sequences, they are counted separately in the score if the positions they are taken from differ.
Input
$T$ $K$
- $1\leq |T| \leq 2\times10^5$
- $T$ is a string consisting only of
0and1 - $1\leq K\leq 10^{18}$
Output
Output the sum of the scores modulo $1000000007=10^9+7$.
Print a newline at the end.
Sample
Sample 1
Input
01 2
Output
54
Since $T=$01$,\ K=2$, the target string $S$ is 0101.
The non-empty alternating subsequences and their scores are as follows.
- Length $1$ :
0( $2$ ways),1( $2$ ways) $\rightarrow$ Score: $1^2\times (2+2)=4$ - Length $2$ :
01( $3$ ways),10( $1$ way) $\rightarrow$ Score: $2^2\times (3+1)=16$ - Length $3$ :
010( $1$ way),101( $1$ way) $\rightarrow$ Score: $3^2\times (1+1)=18$ - Length $4$ :
0101( $1$ way) $\rightarrow$ Score: $4^2\times 1=16$
Note that there are $3$ ways to form 01 (the $3$ ways of choosing the $1$st and $2$nd characters, the $1$st and $4$th characters, and the $3$rd and $4$th characters).
Sample 2
Input
0 1000000000000000000
Output
49
$S$ is a string of $10^{18}$ consecutive 0s.
The non-empty alternating subsequences are the $10^{18}$ ways of choosing $1$ of the 0s.
Therefore, output $1^2\times 10^{18}\mod (10^9+7)=49$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。