自动搬运

查看原文

来自洛谷，原作者为

	Perta broken tower

搬运于2025-08-24 22:54:21，当前版本为作者最后更新于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