P5362 [SDOI2019] 连续子序列

我们定义 $\textbf{T. M.}$ 序列$\{T_n\}$为如下形式得布尔序列： - $T_0=0$； - $T_{2n}=T_n$; - $T_{2n+1}=1-T_n$。 这里我们给出$\textbf{T. M.}$序列得前若干项：$01101001100101101001011001101001\cdots$。 $\textbf{T. M.}$序列是一个无限长度的序列，它有很多连续子序列。 例如$0$，$1$，$10100$，$10011$和$011001$都是它的连续子序列，然而$111$和$1000$却不是它的连续子序列。 现在给定一个布尔序列（01字符串）$S$和一个非负整数$k$，请统计一下一共有多少种$\textbf{T. M.}$序列的连续子序列$T$满足： - $S$是$T$的前缀； - $T$是由$S$额外在右侧添加了恰好$k$项形成的。

无

无

子任务$1$：（$20$分）$1\le T\le 100$，给定布尔序列长度不超过$100$，且$0\le k\le 100$。 子任务$2$：（$20$分）$1\le T\le 100$，给定布尔序列长度不超过$100$，且$0\le k\le 50000$。 子任务$3$：（$60$分）$1\le T\le 100$，给定布尔序列长度不超过$100$，且$0\le k\le 10^{18}$