Minflip Summation

题目描述

我们有一个由 $0$、$1$ 和 $?$ 组成的字符串 $S$。令 $T$ 为 $S$ 的 $K$ 个副本的串联。
通过将 $T$ 中的每个 $?$ 替换为 $0$ 或 $1$，我们可以得到 $2^{Kq}$ 个字符串，其中 $q$ 是 $S$ 中 $?$ 的个数。对于这些字符串中的每一个，求下面的问题的解并将所有答案相加，对 $(10^9+7)$ 取模。

令 $T'$ 为通过替换 $T$ 中的 $?$ 得到的字符串。我们将重复下面的操作直到 $T$ 中的所有字符都相同。至少需要多少次操作？

选择整数 $l$ 和 $r$ 使得 $1 \le l \le r \le |T'|$，并将 $T$ 的第 $l$ 到第 $r$ 个字符取反：$0$ 变为 $1$，$1$ 变为 $0$。

输入格式

输入从标准输入给出，格式如下： $S$ $K$

输出格式

输出一个整数，表示答案。

101
2

2

?0?
1

3

10111?10??1101??1?00?1?01??00010?0?1??
998244353

235562598

提示

$1 \le |S| \le 10^5$ $1 \le K \le 10^9$我们有 $T=$ $101101$，它不包含 $?$，因此我们只需对唯一的 $T'=$ $101101$ 求解。
例如，可以用两次操作将所有字符变为相同：$101101$ $\rightarrow$ $110011$ $\rightarrow$ $111111$。
不可能用一次或更少的操作将所有字符变为相同。
我们有四个可能的 $T'$：$000$、$001$、$100$ 和 $101$。
由于答案可能非常大，请对 $(10^9+7)$ 取模。

标签: AtCoder|abc200F

来源

AtCoder|abc200F