题解：P9324 [EGOI 2022] Chika Wants to Cheat / 出老千

简要题意：

构造 $67000000=6.7 \times 10^7$ 种不同的在 $2 \times 2$ 网格中绘制线段的方式，使得在旋转后仍然能够识别，其中线段的端点必须在整点上，并且除端点外不能经过其他整点。

注意这里的 $2 \times 2$ 网格是有 $9$ 个整点的。

先不考虑旋转。可以算出共有 $\frac{9 \times 8}{2}-2-6=28$ 条不同的线段可以给我们画。那么可能的状态数就有 $2^{28}$ 种。

现在考虑旋转，发现 $28=4 \times 7$，并且刚好可以把 $28$ 条线段分成 $7$ 组，每组里有 $4$ 条线段，且组内的线段可以通过旋转获得。我们把一个状态压成一个 $28$ bits 的整数 $S$，每组线段压在相邻的 bit 里。

这样我们就可以用位运算快速算出一个状态 $S$ 旋转 $90$ 度后的状态 $S'$。

然后我们找出前 $6.7 \times 10^7$ 个满足以下条件的 $S$ 塞进一个 vector 内：

$S$ 小于等于 $S$ 旋转若干次后的状态 $S'$，即 $S \leq \min(S',S'',S''')$。（最小表示法）

构建图形时查表查出第 $i$ 个这样的 $S$。

查询图形时先变为最小表示，在 vector 中二分，这样就可以通过。

实测第 $67000000$ 小的 $S$ 为 $267717551$。

时间复杂度 $O(S_{67000000}+q\log \max n)$。

其中 $S_{67000000}=267717551$，预处理部分常数很小，本地只需 0.5s，时限 2s 随便过。