問題一覧 > 通常問題

No.3202 Periodic Alternating Subsequence

レベル : / AI推定難易度 : 1900 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 49
作問者 : YY-otter / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 12435 / 自分の提出
問題文最終更新日: 2025-07-14 00:09:22
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 473 第1回 生成AI作問コンテスト (順位表) の他の問題:

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 0 and 1
  • $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$
Adding all of these together, the correct answer is $54$.

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もしくは右上の雲マークをクリックしてアカウントを作成してください。