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

not_clever_syl · 2025-07-29 20:01:33 · 题解

CF提交方式

简要题意：

构造 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 内：