Znzryb's Blog
0%

Starters-235-Shift Game

Posted on Edited on

题目大意

题面

Alice 手上有两个长度为 NN 的二进制字符串 AA 和 BB（仅由字符 0 和 1 组成）。

Alice 玩如下游戏。初始时她的分数为 00。每次迭代：

  • 她把两个字符串的首字符乘积加到分数上，即分数增加 A1⋅B1A_1 \cdot B_1。

  • 如果 A1=B1A_1 = B_1，就把 AA 替换为 left_shift(A)\mathrm{left\_shift}(A)。

  • 否则把 BB 替换为 left_shift(B)\mathrm{left\_shift}(B)。

对于二进制字符串 S=S1S2…SLS = S_1 S_2 \ldots S_L，left_shift(S)\mathrm{left\_shift}(S) 定义为删去首字符并追加到末尾：

left_shift(S)=S2S3…SLS1\mathrm{left\_shift}(S) = S_2 S_3 \ldots S_L S_1

现在有 QQ 次独立询问。第 ii 次询问给出整数 KiK_i，需要求出恰好执行 KiK_i 次迭代后 Alice 的分数。各次询问彼此独立，每次都视为从初始字符串 AA、BB 重新开始。

输入格式

  • 第一行一个整数 TT，表示测试用例组数。

  • 每组测试用例共四行：

    • 第一行两个整数 NN、QQ，分别表示字符串长度与询问次数。
    • 第二行是二进制字符串 AA。
    • 第三行是二进制字符串 BB。
    • 第四行 QQ 个空格分隔的整数 K1,K2,…,KQK_1, K_2, \ldots, K_Q。

输出格式

对每组测试用例输出一行，包含 QQ 个空格分隔的整数，第 ii 个整数是执行 KiK_i 次迭代后 Alice 的分数。

数据范围

  • 1≤T≤1041 \leq T \leq 10^4

  • 1≤N,Q≤1061 \leq N, Q \leq 10^6

  • 1≤Ki≤10121 \leq K_i \leq 10^{12}

  • 所有测试用例的 NN 之和、QQ 之和各自不超过 10610^6

  • 时间限制 33 秒；内存限制 1.51.5 GB

样例

样例 1

输入：

1
2
3
4
5
6
7
8
9
2
2 5
01
10
1 3 5 7 9
3 4
101
100
1 6 7 12

输出：

1
2
0 0 1 1 2
1 2 3 4

样例解释

样例 1 的第一组测试用例，前 55 次迭代的详细过程：

  1. A=01, B=10A = \texttt{01},\ B = \texttt{10}。分数增加 0⋅1=00 \cdot 1 = 0。此时 A1≠B1A_1 \neq B_1，令 B←left_shift(B)=01B \leftarrow \mathrm{left\_shift}(B) = \texttt{01}。

  2. A=01, B=01A = \texttt{01},\ B = \texttt{01}。分数增加 0⋅0=00 \cdot 0 = 0。此时 A1=B1A_1 = B_1，令 A←left_shift(A)=10A \leftarrow \mathrm{left\_shift}(A) = \texttt{10}。

  3. A=10, B=01A = \texttt{10},\ B = \texttt{01}。分数增加 1⋅0=01 \cdot 0 = 0。此时 A1≠B1A_1 \neq B_1，令 B←left_shift(B)=10B \leftarrow \mathrm{left\_shift}(B) = \texttt{10}。

  4. A=10, B=10A = \texttt{10},\ B = \texttt{10}。分数增加 1⋅1=11 \cdot 1 = 1。此时 A1=B1A_1 = B_1，令 A←left_shift(A)=01A \leftarrow \mathrm{left\_shift}(A) = \texttt{01}。

  5. A=01, B=10A = \texttt{01},\ B = \texttt{10}。分数增加 0⋅1=00 \cdot 1 = 0。此时 A1≠B1A_1 \neq B_1，令 B←left_shift(B)=01B \leftarrow \mathrm{left\_shift}(B) = \texttt{01}。

前 1,3,5,7,91, 3, 5, 7, 9 次迭代后的累计分数依次为 0,0,1,1,20, 0, 1, 1, 2。

思路讲解

一句话

KK 最大到 101210^{12}，逐步模拟必炸；这题的结构是「run-length 周期 + 首块 + 整圈 + 零头」三段式，外面再套个二分。

状态机：matched / mismatched

得分 A1⋅B1A_1 \cdot B_1 只有在 A1=B1=1A_1 = B_1 = 1 时是 1，其他都是 0。而且「谁前进」完全绑定在 A1=?B1A_1 \stackrel{?}{=} B_1 上，所以过程天然分两态：

  • matched（A1=B1A_1 = B_1）：左移 AA，得分 =A1= A_1

  • mismatched（A1≠B1A_1 \ne B_1）：左移 BB，得分 =0= 0

matched 段持续到 AA 跨过一个 AA-run（A1A_1 翻转），mismatched 段持续到 BB 跨过一个 BB-run（B1B_1 翻转），两态在 run 边界交替。

🎬 Note: 动画：两态循环切换（对应下方 BasicLoop.mp4）——沿时间轴展示 matched ↔ mismatched 的交替节拍，以及每步谁在动、谁在得分。

Video

状态机结构图（题解 PDF p.2）：matched / mismatched 两态 + 切换条件 + 状态表

Phase：一个 matched + 一个 mismatched

把相邻的 matched + mismatched 合成一个 phase。每个 phase 吃掉 AA 的 1 个 run + BB 的 1 个 run，步数 =len(A-run)+len(B-run)= \mathrm{len}(A\text{-run}) + \mathrm{len}(B\text{-run})。

关键不变量：

每过一个 phase，A1,B1A_1, B_1 各翻 1 次，相对关系还原——所以所有 phase 的内部子结构都和第 1 个一样，只需判一次 cA=?cBc_A \stackrel{?}{=} c_B（cA,cBc_A, c_B 就是 A1,B1A_1, B_1 的初始值）。后面零头分类直接吃这条不变量。

跳过首块 + 周期性

AA 从首块内部起步，所以首块是残缺的（长度 L0AL_0^A，与 A1A_1 同字符的极长前缀）。跳过首块后从 L0A mod NL_0^A \bmod N 开始把 AA 当循环串扫一圈，得到完整 run 长度序列 r0A,r1A,…,rkA−1Ar^A_0, r^A_1, \ldots, r^A_{k_A-1}，段长总和 =N= N，之后按段数 kAk_A 为周期重复。BB 侧同构。

注意 段数 kAk_A 和段数 kBk_B 一般不相等，两套预处理彼此独立——同一个 PP（已过 phase 数）在 AA 侧和 BB 侧走的圈数、零头段号可以完全不一样。

🎬 Note: 动画：首块拎出 + 整圈跳跃（对应下方 SkipJump.mp4）——可视化「首块 L0AL_0^A 单独算一份 + 后面按段数周期扫圈」的分解。

Video

A = 00011011 示例（PDF p.3）：首块 L_0^A = 3 单独拎出；跳过首块后循环 run 序列 r^A = (2,1,2,3)，段数 k_A = 4，末段与首块物理同一个 run（同蓝色）

B = 11110000 示例（PDF p.4）：L_0^B = 4，r^B = (4,4)，段数 k_B = 2。注意本例 k_A = 4 ≠ k_B = 2，两侧预处理独立

三段式 O(1)O(1) 函数

走完 PP 个 phase == phase 1 吃首块 ++ 剩下 P−1P - 1 个 phase 按周期跑完。两侧各自拆 P−1=q⋅k+rP - 1 = q \cdot k + r：

fA(P)  =  L0A+qA⋅N+pref_a[rA]f_A(P) \;=\; L_0^A + q_A \cdot N + \mathrm{pref\_a}[r_A]

fB(P)  =  L0B+qB⋅N+pref_b[rB]f_B(P) \;=\; L_0^B + q_B \cdot N + \mathrm{pref\_b}[r_B]

gA(P)  =  L0A⋅cA+qA⋅WA+pref_score_A[rA]g_A(P) \;=\; L_0^A \cdot c_A + q_A \cdot W_A + \mathrm{pref\_score\_A}[r_A]

三段式 O(1) 函数汇总（PDF p.6）：f_A / f_B / g_A 同构，只差「走段长还是得分」「用 A 侧还是 B 侧周期」

WA=∑iriA⋅rateiW_A = \sum_i r^A_i \cdot \mathrm{rate}_i 是一整圈的得分（ratei\mathrm{rate}_i 就是第 ii 段 A1A_1 的值：偶 ii 是 1−cA1 - c_A、奇 ii 是 cAc_A）。P=0P = 0 要直接 return 0，别套公式——不然首块项会白加，而且 P−1=−1P - 1 = -1 做下取整和取模在 C++ 里行为还依赖符号约定，徒增隐患。

二分 + 零头

fA(P)+fB(P)f_A(P) + f_B(P) 关于 PP 单调递增，直接二分找最大 P∗P^* 使 fA(P∗)+fB(P∗)≤Kf_A(P^*) + f_B(P^*) \le K。单查询 O(log⁡K)O(\log K)。

零头 R=K−(fA(P∗)+fB(P∗))R = K - (f_A(P^*) + f_B(P^*)) 落在第 P∗+1P^* + 1 个 phase 里——用那个不变量，查一次 cA=?cBc_A \stackrel{?}{=} c_B 定案：

cAc_A vs cBc_B phase 内部结构 RR 步贡献
cA=cBc_A = c_B 先 matched 后 mismatched min⁡(R, lenA)⋅rateA\min(R,\ \mathrm{len}_A) \cdot \mathrm{rate}_A
cA≠cBc_A \ne c_B 先 mismatched 后 matched max⁡(R−lenB, 0)⋅rateA\max(R - \mathrm{len}_B,\ 0) \cdot \mathrm{rate}_A

口诀：cA=cBc_A = c_B 时 AA 在前，RR 先花在 matched 段；cA≠cBc_A \ne c_B 时 BB 在前，要先熬过 lenB\mathrm{len}_B 步 mismatched 才落到 matched。代码里 A[0] == B[0] 就是在判这个。

uniform 特判

AA 或 BB 全同字符时翻转结构退化（kA=0k_A = 0 之类），奇偶 rate 公式直接出事。把「都 uniform / 只 AA uniform / 只 BB uniform」三类单独闭式处理绕开。通解写完一定要回头扫一遍退化分支，不然很容易暴毙。

复杂度

预处理 O(N)O(N)，单次询问 O(log⁡K)O(\log K)，总 O(N+Qlog⁡K)≈106+106⋅40≈4×107O(N + Q \log K) \approx 10^6 + 10^6 \cdot 40 \approx 4 \times 10^7，稳过 3 s。

📎 动画与源码

solution.tex.txt

solution.pdf — xelatex 编译产物（12 页 A4）

AC代码

心路历程（WA，TLE，MLE……）