1.
P7738 [NOI2021] 量子通信
由于给了字符串生成器，所以串随机
根据鸽笼原理，把串分成 16 块，由于 \(k \le 15\) ，所以必有一个块不变
枚举这个块，然后期望有 \(\frac{n}{2^{16}} \approx 7\) 个，很少，暴力用 \(bitset\) 判断即可
复杂度 \(O(m \times 16 \times \frac{n}{2^{16}} \times \frac{256}{w})\) 可过，不是很卡常
AC
2025.10.14 刷题
深耕网站建设、视觉设计与SEO优化的一线实战洞察。
P7738 [NOI2021] 量子通信
由于给了字符串生成器，所以串随机
根据鸽笼原理，把串分成 16 块，由于 \(k \le 15\) ，所以必有一个块不变
枚举这个块，然后期望有 \(\frac{n}{2^{16}} \approx 7\) 个，很少，暴力用 \(bitset\) 判断即可
复杂度 \(O(m \times 16 \times \frac{n}{2^{16}} \times \frac{256}{w})\) 可过，不是很卡常
AC