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

NaCly_Fish · 2019-09-24 22:25:09 · 题解

出题人怎么一直不发题解啊，，
那我就来水一篇好了（

首先，这题看起来时什么 \Theta(2^{|S|}) 之类的做法，然而实际上就是 \Theta(n|S|/w) 的 bitset 大暴力。

做法也就是开一个 10^9 的数组，对于 S 中的每个数 k，把 k 的倍数都设为 1，统计数组中有多少组 3 个连续的 1 即是答案。

然后把这个过程用 bitset 优化一下就可以了（
另外要注意的一点，x 是正整数，或许要把第 0 项的贡献判掉

ps：这个东西和分块的思想很像，不过是基于CPU的运算优化的。

代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#define N 1000000003
#define reg register
using namespace std;

unsigned long long bs[(N>>6)+10];
unsigned long long tmp[65];
int n,m,s,l,ans;

inline int count(unsigned long long x){
    reg int res = 0;
    while(x){
        res += x&1;
        x >>= 1;
    }
    return res;
}

int main(){
    scanf("%d%d",&n,&s);
    m = (n>>6)+1;
    while(s--){
        scanf("%d",&l);
        if(l<64){ //两种情况判一下,保证加入的复杂度是 n/w
            memset(tmp,0,sizeof(tmp));
            for(reg int i=0;i<(l<<6);i+=l)
                tmp[i>>6] |= 1ull<<(i&63); //加入的数比较小,开另一个数组,作为重复单元
            for(reg int i=0;i<=m;i+=l)
            for(reg int j=0;j<l;++j)
                bs[i+j] |= tmp[j];    
        }else{
            for(reg int i=0;i<=n;i+=l)
                bs[i>>6] |= 1ull<<(i&63);
        }
    }
    --m;
    if((n&63)!=63) bs[m] &= (1ull<<(n+1-(m<<6)))-1; //特判一下最后一块
    bs[0] &= -2ull; //除去第 0 项
    for(reg int i=0;i<=m;++i) ans += count(bs[i]&(bs[i]<<1)&(bs[i]<<2));
    for(reg int i=1;i<=m;++i) ans += count(bs[i]&(bs[i-1]>>62)&((bs[i-1]>>63)|(bs[i]<<1)));
    printf("%d",ans);
    return 0;
}