题解：P5539 【XR-3】Unknown Mother-Goose

· · 题解

前言

世界があたしを拒んでも，

今、愛の唄 歌わせてくれないかな？

思路

首先有一个显然的暴力，设集合 S 中的第 i 个数为 a_i，那我们只需要把所有小于等于 n 的 a_i 的倍数全部用一个 bool 数组记录下来，再看这个 bool 数组内有多少组连续 3 个的 1 即可。

虽然这样是可行的，但这个方法显然最坏是 O(n|S|)，在 n\le 10^9 的数据下并不能通过，就算不论时间复杂度，空间也不能接受。

不过如果你会 bitset 的话，显然能想到这个方法可以使用 bitset 优化空间。bitset 的原理就是对一个整型变量，将其的每一个二进制位都当作一个 bool 来使用。使用 bitset 处理的空间复杂度为 O(\frac{n}{w})，其中 w 为 bitset 所优化的位数。使用 STL 中的 bitset，w=32。但我们可以使用手写 bitset 的方式来把 w 优化到 64。

但是这样仍然无法通过，因为如果 a_i=1，这意味着我们仍要循环 n 次来找到所有倍数，我们的时间复杂度在 bitset 里也依然为 O(n|S|)。什么方法来优化呢？有的，我们可以分类讨论。

输出时，分类为全部在同一个整型内，一个在左边的整型而两个在右边的整型，两个在左边的整型而一个在右边的整型这三种情况解决即可。具体可以看代码的输出部分。

最后总时间复杂度最坏为 O(\frac{n}{w}|S|)。在 w=64 的情况下，大约等于 3\times 10^8，大致可以卡过去。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
unsigned long long p[16500005], h[70];
int n, s, u, m, ans;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> s;
    m = n >> 6;//bitset 的整型数量
    while (s--) {
        cin >> u;
        if (u < 64) {//处理 < 64 的部分
            for (int i = 0; i < (u << 6); i += u) {
                h[i >> 6] |= 1ull << (i & 63);//这里相当于 %64，但是 &63 比 %64 快不少
            }
            for (int i = 0; i <= m + 1; i += u) for (int j = 0; j < u; j++)p[i + j] |= h[j];
            for (int i = u - 1; i >= 0; i--) {
                h[i] = 0;
            }
        } else {//处理 >= 64 的部分
            for (int i = 0; i <= n; i += u) {
                p[i >> 6] |= 1ull << (i & 63);
            }
        }
    }
    p[0] &= p[0] - 1;//去掉第0位
    if ((n & 63) != 63) p[m] &= (1ull << ((n & 63) + 1)) - 1;//去掉第n位以外的位
    for (int i = 0; i <= m; i++) ans +=  __builtin_popcountll((p[i]) & (p[i] >> 1) & (p[i] >> 2));//在同一整型内 
    for (int i = 1; i <= m; i++) ans +=  __builtin_popcountll((p[i]) & (p[i - 1] >> 62) & ((p[i] << 1) | p[i - 1] >> 63));//不在同一整型内
    // __builtin_popcountll() 可以在 O(1) 的时间复杂度内求出一个 long long 的二进制里 1 的数量 
    cout << ans;
    return 0;
}