P10066 [CCO2023] Binaria 题解

Perta · 2024-01-19 16:02:52 · 题解

设题面中二进制字符串为 S，SMS 为 a，则 a_i=\sum_{j=i}^{i+k-1}S_j。

发现 a_{i+1}-a_i=S_{i+k}-S_{i}，不妨利用这个关系建图。将 i 向 i+k 连一条边权为 S_{i+k}-S_i 的边，这样会形成 k 个连通块。由于 a_i\in\{0,1\}，对于每个连通块中的数有如下限制：

• 若 x 所在连通块含边权不为 0 的边，则 a_x 的值确定；
• 否则，连通块内的所有数 值相同。

这个很好理解。比如 i 向 i+k 连了一条边权为 1 的边，那么就只有一种可行解：S_i=0,S_{i+k}=1。那么一个连通块确定一个数就可以确定剩下的数。

对于没有被确定的连通块（只含边权为 0 的边），仅要求所有数的值相同，但是要满足 a_i=\sum_{j=i}^{i+k-1}S_j 的限制。由于我们是通过这个限制建的图，只需要满足 a_1 即可。

只考虑 1\sim k。设当前已经确定的 \sum S_j 为 t_1，未确定的个数为 t_2，则答案为 \dbinom{t_2}{a_1-t_1}。注意，存在 a_i\notin\{0,1\} 时无解。

复杂度理论上是 O(n) 的，但是煮波太懒了加了个并查集。

Code