P8438 题解

· · 题解

cz 过了，用的是点名被卡但是卡卡常就能冲过去的写法。

本题的最大难点在于，对洛谷评测机的效率的高度了解。

首先，不难根据题目中对于 v(S) 的定义，暴力地计算出最后的结果。因为答案是对 2^{64} 取模，因而可以直接采用 unsigned long long 进行全程的运算，直接自然溢出啥事没有。

如果你手写去拆二进制速度是慢的。这里可以使用内建函数 __builtin_ffs(x)，返回 x 中最后一个为 1 的位是从后向前的第几位。可以将拆二进制位的一个 \log 的复杂度去掉。

参考代码如下：

for (int i=1;i<(1<<n);i++)
{
    for (int j=__builtin_ffs(i);j;j--)
        ret^=a[j];
    ans^=ret*i;
}

如果你提交这个代码，你会发现在 n=25 的情况下跑了 79ms。而当 n=30 的情况下应该要多跑 32 倍的时间，也就是 2.5s。

我们考虑对这个循环进行一定的优化。我们考虑对于相邻 4 个正整数的二进制串，那么它们的末尾将会是如下的循环：\texttt{00}、\texttt{01}、\texttt{10}、\texttt{11}。

而对于 \texttt{01}、\texttt{10}、\texttt{11} 的部分我们可以只需要分别让 ret 异或上 a[1]、a[1] xor a[2]、a[1] 即可。对于 \texttt{00} 的部分，再暴力跑 for (int j=__builtin_ffs(i);j;j--) 这层循环。可以让调用 __builtin_ffs() 函数的次数变成原来的 \dfrac{1}{4}，而且也减少了新定义变量的次数。

此外，将对 ret 和 ans 两个变量的计算进行了上述的展开，本质也会加速 CPU 的流水线调度，进一步地去优化常数。这样，你的代码就足以通过此题了。实际上这样做的常数是相当优秀的（循环展开相当于除以 4，对 __builtin_ffs() 循环的优化也大幅度减小了常数，而且本身这个循环就很难跑到 n 次的）。如果你实测一下的话会发现，内层循环跑了恰好 2^n 次，因而可以通过本题。

代码如下：

int n;

unsigned long long a[33],ret=0,ans;

int main()
{
    n=read();
    for (int i=1;i<=n;i++)
        a[i]=read();
    int i;
    for (i=1;i+4<(1<<n);)
    {
        ret^=a[1];
        ans^=ret*(i++);
        ret^=a[1]^a[2];
        ans^=ret*(i++);
        ret^=a[1];
        ans^=ret*(i++);
        for (int j=__builtin_ffs(i);j;j--)
            ret^=a[j];
        ans^=ret*(i++);
    }
    ret^=a[1];
    ans^=ret*(i++);
    ret^=a[1]^a[2];
    ans^=ret*(i++);
    ret^=a[1];
    ans^=ret*(i++);
    cout << ans << endl;
    return 0;
}

实际上，洛谷评测机的速度是足以支持在 1 秒内进行 1.2 \times 10^9 次 unsigned long long 类型变量相乘并且自然溢出的。所以如果是小常数 O(2^n)，n=30 是能跑的。

这里就需要指出另外一种做法：将高低位拆分之后暴力合并去计算。这样的做法的时间复杂度也是很高的，因为它要将两个 65536 大小的数组去合并运算。但是实际上跑的是非常非常快的。

for(i=0;i<lim1;i++)
{
    for(j=0;j<lim2;j++)
            ans^=(dp[i]^dp2[j])*(unsigned long long)(i+j*lim1);
}

实际上我们可以使用如下代码获得洛谷评测机的 CPU 型号：

#include <stdint.h>
#include <iostream>
#include <cpuid.h>
static void cpuid(uint32_t func, uint32_t sub, uint32_t data[4]) {
    __cpuid_count(func, sub, data[0], data[1], data[2], data[3]);
}
int main() {
    uint32_t data[4];
    char str[48];
    for(int i = 0; i < 3; ++i) {
        cpuid(0x80000002 + i, 0, data);
        for(int j = 0; j < 4; ++j)
            reinterpret_cast<uint32_t*>(str)[i * 4 + j] = data[j];
    }
    std::cout << str;
}

可得洛谷 CPU 型号为 Intel(R) Xeon(R) Platinum 8369HC CPU @ 3.30GHz。然而由于这个是阿里云定制 CPU，其实很难查到它的参数数据。

但是与其同一代的 CPU Intel(R) Xeon(R) Platinum 8360HC CPU @ 3.00GHz 的 Cache 大小是 33MB，而有着 24 个核心，也就是说每个核心有着 1.375MB 的高速缓存，足以存下两个大小为 65536 的 unsigned long long 数组。当这些数组进入高速缓存（实际上应该是 L3 cache）之后，其读写效率是显著快于在内存中的读写的（快 4 倍左右）。此外，合并的过程做的都是连续的内存访问，有着很好的空间局部性，也减少了常数。因而，它在 O(2^n) 的复杂度下能够跑的很快。