自动搬运

查看原文

来自洛谷，原作者为

	Loser_Syx 不可逆の方が美しいから

搬运于2025-08-24 22:54:07，当前版本为作者最后更新于2024-01-09 22:00:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

很暴力的一道题。

你考虑 bitset 维护当前已经确定的答案，发现每次其实就是左移 $i$ 位，每轮 $n\div i$ 次，再维护一个 ? 的答案，直接再看一下左移完 $i$ 位后是否存在新的交集然后更新即可。

复杂度显然是 $O(\frac{n^2\ln n}{\omega})$ 的，超时得很惨。

但是你可以考虑根号分治，前面 $i \leq \sqrt n$ 的数你可以直接暴力（因为让 bitset 搞每次次数 $\geq \sqrt n$），这么一段是 $O(n \sqrt n)$ 的复杂度，后面 $i > \sqrt n$ 的部分选择 bitset，复杂度退化为 $O(\frac{n^2 \ln \sqrt n}{\omega})$，总复杂度为两段之和，可以通过。

const int N=1e5+19;
bitset<N> ans, maybe, now;
signed main() {
	int n; string s;
	cin >> n >> s;
	int sq=sqrt(n);
	s=" "+s;
	for (int i=1;i<=n;++i) {
		if (s[i]=='1') ans[i]=1;
		else if (s[i]=='?') maybe[i]=1;
	}
	for (int i=1;i<=n;++i) {
		now=ans;
		if (i <= sq) {
			for (int j=i+1;j<=n;++j) if (s[j]=='?'&&now[j-i]) now[j]=1;
		} else {
		for (int j=i;j<=n;j+=i) {
			now=now|((now<<i)&maybe);
		} }
		write(now.count(), '\n');
	}
	return 0;
}