Starters-235-Shift Game（这个移动看起来没什么规律，但是实际上看了视频以后，你会发现按段来切分，实际上 A 动的时候 B 不动，B 动的时候 A 不动） · znzryb
## 题目大意
## 题面
Alice 手上有两个长度为 $N$ 的二进制字符串 $A$ 和 $B$（仅由字符 `0` 和 `1` 组成）。
Alice 玩如下游戏。初始时她的分数为 $0$。每次迭代：
- 她把两个字符串的首字符乘积加到分数上，即分数增加 $A_1 \cdot B_1$。
- 如果 $A_1 = B_1$，就把 $A$ 替换为 $\mathrm{left\_shift}(A)$。
- 否则把 $B$ 替换为 $\mathrm{left\_shift}(B)$。
对于二进制字符串 $S = S_1 S_2 \ldots S_L$，$\mathrm{left\_shift}(S)$ 定义为删去首字符并追加到末尾：
$$
\mathrm{left\_shift}(S) = S_2 S_3 \ldots S_L S_1
$$
现在有 $Q$ 次独立询问。第 $i$ 次询问给出整数 $K_i$，需要求出恰好执行 $K_i$ 次迭代后 Alice 的分数。各次询问彼此独立，每次都视为从初始字符串 $A$、$B$ 重新开始。
## 输入格式
- 第一行一个整数 $T$，表示测试用例组数。
- 每组测试用例共四行：
- 第一行两个整数 $N$、$Q$，分别表示字符串长度与询问次数。
- 第二行是二进制字符串 $A$。
- 第三行是二进制字符串 $B$。
- 第四行 $Q$ 个空格分隔的整数 $K_1, K_2, \ldots, K_Q$。
## 输出格式
对每组测试用例输出一行，包含 $Q$ 个空格分隔的整数，第 $i$ 个整数是执行 $K_i$ 次迭代后 Alice 的分数。
## 数据范围
- $1 \leq T \leq 10^4$
- $1 \leq N, Q \leq 10^6$
- $1 \leq K_i \leq 10^{12}$
- 所有测试用例的 $N$ 之和、$Q$ 之和各自不超过 $10^6$
- 时间限制 $3$ 秒；内存限制 $1.5$ GB
## 样例
**样例 1**
输入：
```
2
2 5
01
10
1 3 5 7 9
3 4
101
100
1 6 7 12
```
输出：
```
0 0 1 1 2
1 2 3 4
```
## 样例解释
样例 1 的第一组测试用例，前 $5$ 次迭代的详细过程：
1. $A = \texttt{01},\ B = \texttt{10}$。分数增加 $0 \cdot 1 = 0$。此时 $A_1 \neq B_1$，令 $B \leftarrow \mathrm{left\_shift}(B) = \texttt{01}$。
1. $A = \texttt{01},\ B = \texttt{01}$。分数增加 $0 \cdot 0 = 0$。此时 $A_1 = B_1$，令 $A \leftarrow \mathrm{left\_shift}(A) = \texttt{10}$。
1. $A = \texttt{10},\ B = \texttt{01}$。分数增加 $1 \cdot 0 = 0$。此时 $A_1 \neq B_1$，令 $B \leftarrow \mathrm{left\_shift}(B) = \texttt{10}$。
1. $A = \texttt{10},\ B = \texttt{10}$。分数增加 $1 \cdot 1 = 1$。此时 $A_1 = B_1$，令 $A \leftarrow \mathrm{left\_shift}(A) = \texttt{01}$。
1. $A = \texttt{01},\ B = \texttt{10}$。分数增加 $0 \cdot 1 = 0$。此时 $A_1 \neq B_1$，令 $B \leftarrow \mathrm{left\_shift}(B) = \texttt{01}$。
前 $1, 3, 5, 7, 9$ 次迭代后的累计分数依次为 $0, 0, 1, 1, 2$。
## 思路讲解
### 一句话
$K$ 最大到 $10^{12}$，逐步模拟必炸；这题的结构是「run-length 周期 + 首块 + 整圈 + 零头」三段式，外面再套个二分。
### 状态机：matched / mismatched
得分 $A_1 \cdot B_1$ 只有在 $A_1 = B_1 = 1$ 时是 1，其他都是 0。而且「谁前进」完全绑定在 $A_1 \stackrel{?}{=} B_1$ 上，所以过程天然分两态：
- **matched**（$A_1 = B_1$）：左移 $A$，得分 $= A_1$
- **mismatched**（$A_1 \ne B_1$）：左移 $B$，得分 $= 0$
matched 段持续到 $A$ 跨过一个 $A$-run（$A_1$ 翻转），mismatched 段持续到 $B$ 跨过一个 $B$-run（$B_1$ 翻转），两态在 run 边界交替。
> 🎬 **Note**: **动画：两态循环切换**（对应下方 [BasicLoop.mp](http://basicloop.mp/)4）——沿时间轴展示 matched ↔ mismatched 的交替节拍，以及每步谁在动、谁在得分。
[Video](https://media.znzryb.com/20260423-a376b218/BasicLoop_da4eebc3.mp4)
### Phase：一个 matched + 一个 mismatched
把相邻的 matched + mismatched 合成一个 **phase**。每个 phase 吃掉 $A$ 的 1 个 run + $B$ 的 1 个 run，步数 $= \mathrm{len}(A\text{-run}) + \mathrm{len}(B\text{-run})$。
关键不变量：
> 每过一个 phase，$A_1, B_1$ 各翻 1 次，**相对关系还原**——所以所有 phase 的内部子结构都和第 1 个一样，只需判一次 $c_A \stackrel{?}{=} c_B$（$c_A, c_B$ 就是 $A_1, B_1$ 的初始值）。后面零头分类直接吃这条不变量。
### 跳过首块 + 周期性
$A$ 从首块内部起步，所以首块是**残缺**的（长度 $L_0^A$，与 $A_1$ 同字符的极长前缀）。**跳过首块**后从 $L_0^A \bmod N$ 开始把 $A$ 当循环串扫一圈，得到完整 run 长度序列 $r^A_0, r^A_1, \ldots, r^A_{k_A-1}$，段长总和 $= N$，之后按段数 $k_A$ 为周期重复。$B$ 侧同构。
注意 **段数** $k_A$ **和段数** $k_B$ **一般不相等**，两套预处理彼此独立——同一个 $P$（已过 phase 数）在 $A$ 侧和 $B$ 侧走的圈数、零头段号可以完全不一样。
> 🎬 **Note**: **动画：首块拎出 + 整圈跳跃**（对应下方 [SkipJump.mp](http://skipjump.mp/)4）——可视化「首块 $L_0^A$ 单独算一份 + 后面按段数周期扫圈」的分解。
[Video](https://media.znzryb.com/20260423-a376b218/SkipJump_1443c1af.mp4)
### 三段式 $O(1)$ 函数
走完 $P$ 个 phase $=$ phase 1 吃首块 $+$ 剩下 $P - 1$ 个 phase 按周期跑完。两侧各自拆 $P - 1 = q \cdot k + r$：
$$
f_A(P) \;=\; L_0^A + q_A \cdot N + \mathrm{pref\_a}[r_A]
$$
$$
f_B(P) \;=\; L_0^B + q_B \cdot N + \mathrm{pref\_b}[r_B]
$$
$$
g_A(P) \;=\; L_0^A \cdot c_A + q_A \cdot W_A + \mathrm{pref\_score\_A}[r_A]
$$
> 🎬 **Note**: **动画：预处理数组构造**（对应下方 Preprocess.mp4）——动态展示两侧 run 长度序列、pref_a / pref_b 前缀和、整圈得分 W_A 是怎么一步步填出来的，三段式 O(1) 公式里的参数全部在这步落地。
[Video](https://media.znzryb.com/20260423-a376b218/Preprocess_9bda38e6.mp4)
$W_A = \sum_i r^A_i \cdot \mathrm{rate}_i$ 是一整圈的得分（$\mathrm{rate}_i$ 就是第 $i$ 段 $A_1$ 的值：偶 $i$ 是 $1 - c_A$、奇 $i$ 是 $c_A$）。$P = 0$ 要**直接 return 0**，别套公式——不然首块项会白加，而且 $P - 1 = -1$ 做下取整和取模在 C++ 里行为还依赖符号约定，徒增隐患。
### 二分 + 零头（这个二分应该是单纯我们不大能推出来这个最大能走）
$f_A(P) + f_B(P)$ 关于 $P$ 单调递增，直接二分找最大 $P^*$ 使 $f_A(P^*) + f_B(P^*) \le K$。单查询 $O(\log K)$。
零头 $R = K - (f_A(P^*) + f_B(P^*))$ 落在第 $P^* + 1$ 个 phase 里——用那个不变量，查一次 $c_A \stackrel{?}{=} c_B$ 定案：
| $c_A$ vs $c_B$ | phase 内部结构 | $R$ 步贡献 |
| --- | --- | --- |
| $c_A = c_B$ | 先 matched 后 mismatched | $\min(R,\ \mathrm{len}_A) \cdot \mathrm{rate}_A$ |
| $c_A \ne c_B$ | 先 mismatched 后 matched | $\max(R - \mathrm{len}_B,\ 0) \cdot \mathrm{rate}_A$ |
口诀：$c_A = c_B$ 时 $A$ 在前，$R$ 先花在 matched 段；$c_A \ne c_B$ 时 $B$ 在前，要先熬过 $\mathrm{len}_B$ 步 mismatched 才落到 matched。代码里 `A[0] == B[0]` 就是在判这个。
### uniform 特判
$A$ 或 $B$ 全同字符时翻转结构退化（$k_A = 0$ 之类），奇偶 rate 公式直接出事。把「都 uniform / 只 $A$ uniform / 只 $B$ uniform」三类单独闭式处理绕开。**通解写完一定要回头扫一遍退化分支**，不然很容易暴毙。
### 复杂度
预处理 $O(N)$，单次询问 $O(\log K)$，总 $O(N + Q \log K) \approx 10^6 + 10^6 \cdot 40 \approx 4 \times 10^7$，稳过 3 s。
### 📎 动画与源码
[solution.tex.txt](https://prod-files-secure.s3.us-west-2.amazonaws.com/991df910-3fbe-4ef6-8683-a51746ed5b66/3561e37d-c96e-45b2-b86d-23c9c90e393e/solution.tex.txt?X-Amz-Algorithm=AWS4-HMAC-SHA256&X-Amz-Content-Sha256=UNSIGNED-PAYLOAD&X-Amz-Credential=ASIAZI2LB466QRBFAE5Y%2F20260429%2Fus-west-2%2Fs3%2Faws4_request&X-Amz-Date=20260429T072201Z&X-Amz-Expires=3600&X-Amz-Security-Token=IQoJb3JpZ2luX2VjECcaCXVzLXdlc3QtMiJGMEQCIAuOXYzPHE7%2FL4%2Ff6C4S5R7gFtDk5JBpHSNhbHDH9FpfAiA8Kuws%2F%2FhbYGu%2BGCdvKhdR2z1nr2Owkzd%2FW9v6bFZzViqIBAjw%2F%2F%2F%2F%2F%2F%2F%2F%2F%2F8BEAAaDDYzNzQyMzE4MzgwNSIMc3ImBkdEyUvo1mibKtwD6rmuTJH6K%2FUAfmymZZnAibcc0qrFAUn8Edt0HESxRl%2F61V7eeO7UpX3MGbqybY6djC1rOHJBpfafDPSL%2BS0S5GU8fBXVkfQYz7P5syPSNz%2Fb6SHv3GzinMJTHHwx1O7aRW2Hp0wWtv63muCK3ctcZ%2B%2FTWGQ%2F4DQF9ei2e2gzFmHB%2Fuu5Jugi7i%2BY8ySXDcYryPP3TtVPcigkHE7P68kS%2BRG2M3FMlPPDHE8Zz4j%2BF0VkB21hP2a0htUcg1P76L70lwEY5rM9j8ZFxEDjDwZ2l7mQl1kA7RSikqh4%2BBr90%2FS2uG7ckpKXdD3LGLQTZUIuWs22ATj0vxWn3%2FO3DOvsj7AtirWbwpkYlPjucdMrwT9OAIwgDW%2B%2Fh0b398YrbVNwqOclhe3YdoANK861u3Tlu3trug6rV1z59w5TTe18WLV6tdFxhMI%2B84VhVxNJTULARDbL27JT9qBzEQS7yoT1auMzpmRJXgih%2B0Xkr3O1yS2aQZ7USlt6TGmtcTkqFMlHvlt8rpHZkRpnUzYn06lUSS1SNEZXFA66dEey86NfM1w3YRRE7hAl1K7LbEKOcbLHrK3YmBMeXHF6s0XhtiaLPQJGlIlaqqSGSZu6lH9EIohx0CJ%2FK%2FR%2BNvB%2F6yIw8drGzwY6pgF40loRrZF8Fo0Yy1bZ%2BisvwNZgLmb%2BjsqeFVVV%2FwAOcsPgHnI945NIvQwfhzbdOlZZGJ5tnEq4qP1aP0%2BIrnw4FRpnOhlPin%2Bk2Xa%2BBeB3akMtcMVeseeU%2BBijWyvvz74Mcm17ale6UThN6uBIlYcpXlDPHTqv77mLhPhe2lXy5cGUSBDA3mSOdfqfx%2Bk0HFe7wWvRMkz%2Bs%2BT%2FfLbwCjfMpx1fDW2y&X-Amz-Signature=ae2cbceca4bec7365c462e78dcb933b52afd1760cb1aaf228caf0a56d651087a&X-Amz-SignedHeaders=host&x-amz-checksum-mode=ENABLED&x-id=GetObject)
[solution.pdf — xelatex 编译产物（12 页 A4）](https://media.znzryb.com/20260423-a376b218/solution_2bb72bc4.pdf)
## AC代码
> 🎬 **Note**: **动画：代码走读**（对应下方 CodeWalkthrough.mp4）——按执行顺序高亮核心函数（预处理、f_A/f_B/g_A、二分主框架、零头分类），配合上面思路节的三段式公式一起看。
[Video](https://media.znzryb.com/20260423-a376b218/CodeWalkthrough_18212782.mp4)
::: 源代码
```cpp
```
:::
## 心路历程（WA，TLE，MLE……）