题目概述

这是一个交互题，有 $N$ 个房间和 $N$ 个开关，每个开关控制一个特定的房间。开关与房间的对应关系由一个排列 $p$ 决定：开关 $s$ 控制房间 $p_s$。

目标：找出控制**第一个房间（房间0）和最后一个房间（房间N-1）**的两个开关。

限制：最多进行30次"旅程"（查询）。

---

交互过程

每次查询：

• 你输出一个长度为 $N$ 的 0/1 字符串，表示哪些开关打开
• 交互器返回一个整数 $\ell$，表示乘客尖叫次数
• 尖叫发生在相邻房间亮度变化时（亮→暗 或 暗→亮）

最终输出：两个开关编号 $A$ 和 $B$，使得 $\{p_A, p_B\} = \{0, N-1\}$。

---

关键观察

尖叫次数的意义

设打开的开关集合为 $S$，则亮着的房间集合是 $\{p_s \mid s \in S\}$。

尖叫次数 = 相邻房间亮度不同的次数。

重要性质：如果第一个房间和最后一个房间的亮度相同，那么尖叫次数是偶数；如果不同，则是奇数。

证明：从房间0到房间N-1，亮度变化的次数如果是奇数，那么起点和终点的亮度必然不同。

---

算法思路

步骤1：找到包含目标开关的块

使用二分查找的思想，但这里是对开关编号进行分组。

1. 外层二分：确定一个最小的 $k$，使得当按照模 $k$ 分组打开开关时，尖叫次数为奇数。

   • 这意味着控制房间0和房间N-1的两个开关在模 $k$ 下属于不同的半组
   • 初始 $k$ 从大于 $N$ 的2的幂开始，不断减半

2. 内层二分：在确定的 $k$ 值下，找到具体的偏移量 $l$，使得区间 $[l, l+k-1]$ 包含两个目标开关。

步骤2：在块内定位两个开关

现在我们知道两个目标开关在区间 $[l, l+k-1]$ 中，且分别位于前半部分和后半部分。

使用二分查找分别在前半部分和后半部分中找到具体的开关：

• 对前半部分 $[l, l+k/2-1]$ 进行二分
• 对后半部分 $[l+k/2, l+k-1]$ 进行二分

每次二分时，翻转当前考虑区间内开关的状态，检查尖叫次数的奇偶性变化。

---

算法详解

核心函数

mod_k_check(l, r, k, skip_q)

检查模 $k$ 分组的情况：

• 对于 $i \in [l, r]$，如果 $i \bmod k < k/2$，则打开开关 $i$
• 返回尖叫次数的奇偶性

binary_search(l, r)

在区间 $[l, r]$ 内二分查找目标开关：

• 翻转左半部分开关状态
• 如果尖叫次数奇偶性不变，说明目标在左半部分
• 否则在右半部分

主流程

// 步骤1：找到合适的k
k = 大于N的最小2的幂
while true:
    按模k分组打开开关
    if 尖叫次数为奇数: break
    else: k /= 2

// 步骤2：找到偏移量l  
kk = k/2
while kk >= k:
    测试区间[l, l+kk-1]和[l+kk, l+2*kk-1]
    根据奇偶性调整l
    kk /= 2

// 步骤3：在最终区间内二分查找两个开关
a = 在前半部分二分查找
b = 在后半部分二分查找

---

正确性分析

为什么这样能找到目标开关？

1. 奇偶性原理：只有当房间0和房间N-1的亮度不同时，尖叫次数才是奇数
2. 分组技巧：通过模 $k$ 分组，可以判断两个目标开关是否在同一半组
3. 二分查找：在确定的区间内，通过翻转部分开关状态，可以精确定位目标

查询次数分析

• 步骤1：最多 $\lceil \log_2 N \rceil$ 次查询
• 步骤2：最多 $\lceil \log_2 N \rceil$ 次查询
• 步骤3：每个二分查找需要 $\lceil \log_2 k \rceil$ 次查询，总共约 $2\lceil \log_2 N \rceil$ 次

总查询次数：约 $4\lceil \log_2 N \rceil$，对于 $N \le 30000$，这远小于30次。

---

样例解析

样例1

N=5, p=[2,1,0,3,4]

步骤：
1. 找到k=4（使得尖叫次数为奇数的最大分组）
2. 找到l=0（包含两个目标开关的区间）
3. 在[0,3]中二分查找：
   - 前半[0,1]中找到开关2
   - 后半[2,3]中找到开关4
输出：2 4

样例2

N=3, p=[2,0,1]

步骤：
1. 找到k=2
2. 找到l=0  
3. 在[0,1]中二分找到开关0和1
输出：0 1

---

优化技巧

1. 位运算优化：使用2的幂进行分组，便于二分
2. 奇偶性判断：只关心尖叫次数的奇偶性，不关心具体数值
3. 状态复用：在二分查找中重复利用部分查询结果

---

总结

这道题的核心技巧在于：

1. 利用奇偶性：通过尖叫次数的奇偶性判断端点房间亮度是否相同
2. 分层二分：先确定包含目标的大区间，再在区间内精确定位
3. 分组查询：使用模运算进行高效的分组测试

这种"奇偶性判断 + 分层二分"的方法，在解决需要定位多个目标的交互题中非常有效，特别是在查询次数有限的情况下。