P10040

Loser_Syx · 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;
}