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

· · 题解

先转化一下题意，题目要求的是把 S 集合中所有的数的倍数标记之后，连续 3 个都被标记的位置的数量，于是可以得到一个 O(n|S|) 的做法，考虑进行二进制压位优化手写 bitset。

对于集合中不小于 64 的元素 x，枚举其倍数进行标记复杂度为 \frac{n}{x}，因为 x\ge64，故最坏情况复杂度为 \frac{n}{64}。

对于集合中小于 64 的元素 x，把要进行标记的位置压进 unsigned long long，循环节的长度一定不大于 x，所以可以把一个循环节处理出来然后对标记数组或上这个循环节就可以做到 O(64+x+\frac{n}{64})。

原数组和其左移 1 位的数组和左移 2 位的数组或起来之后 1 的个数就是答案，然后使用 unsigned long long 可以达到 O(\frac{n}{64})。

总时间复杂度(最坏情况) O(128|S|+\frac{n(|S|+1)}{64})，算出来大概 3.3\times10^8，因为内存访问还是比较连续的所以能过。

现在过的应该都类似于这种做法，大部分时间都是在 \frac{n(|S|+1)}{U}，造成运行时间差异的主要原因是代码的常数，这里就讲一下怎么卡常。

此题输入输出量并不大，所以 IO 复杂度可以忽略写了 fread 也没关系；可能因为开了 O2，inline 和 register 优化也不大。下面是几个常数优化比较大的地方：

尽量避免循环内除法、取模运算。

众所周知，除法、取模是非常慢的，特别是还放在循环里面跑满了 \frac{n|s|}{64} 遍。
比如下面的两段代码是等效的，但是前者对应的是 15.42s，而后者是 8.13s，比前面的快了 7.29s。

int r=(n>>6)/k*k;
for(int i=0;i<r;i++)vis[i]|=tmp[i%k];//15.42s
int r=(n>>6)/k*k;
for(int i=0;i<r;i+=k)for(int j=0;j<k;j++)vis[i+j]|=tmp[j];//8.13s

使用较快的统计 1 的个数的方式。

统计二进制 1 的个数有几种方式，下面放一下本地测试情况，测试数据为随机 01 串，长度为 10^9，重复计算 10 次取时间和。

  1. 每次去除最低位，递归实现。代码：f(i){return i?f(i&(i-1))+1:0;}
    运算时间和 1 的位数相关，最慢，3300ms 左右。
  2. 每次去除最低位，循环实现。代码：while(i)++cnt,i&=i-1;
    运算时间还是和 1 的个数相关，很慢，3100ms 左右。
  3. 转 bitset 使用 count 函数。代码：vis.count();
    因为使用 bitset，常数降为 \frac{1}{64}，较快，600ms 左右。
  4. 使用位运算加速的某种 \log\log n 的做法。 
    int f(unsigned long long i)
{
i=(i&0x5555555555555555)+(i>>1&0x5555555555555555),
i=(i&0x3333333333333333)+(i>>2&0x3333333333333333),
i=(i&0x0f0f0f0f0f0f0f0f)+(i>>4&0x0f0f0f0f0f0f0f0f),
i=(i&0x00ff00ff00ff00ff)+(i>>8&0x00ff00ff00ff00ff),
i=(i&0x0000ffff0000ffff)+(i>>16&0x0000ffff0000ffff);
return i+(i>>32);
}//450ms
  5. 玄学东西，__builtin_popcountll(i)
    运行速度最快，300ms 以内，但是有双下划线所以联赛不能用。

经过卡常，可以做到总时间卡进 6.94s，代码，下面再放一些更玄学的东西：

#include<immintrin.h>
#pragma GCC target("avx2")

没错就是要用指令集。 注意，平常用可以，正式比赛的时候千万别用，用了会原地AFO。

加了指令集头文件之后，就可以使用指令集了，不知道为什么总有些人指令集头文件乱加，加完又不用指令集还说加了指令集，这里指令集主要用在优化打标记的过程，可以做到在一次运算的时间内对 256 位进行或运算，也就是这句话：vism[i+j]=_mm256_or_si256(vism[i+j],tmpm[j])。

经过指令集优化之后，复杂度变为 O(\frac{n|S|}{256}+\frac{n}{64})，可以在上面的基础上再优化 1.23s，放上目前最优解代码前面说过的优化不大的东西还是加上去了。