自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 22:39:04，当前版本为作者最后更新于2022-07-18 13:13:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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)$ 的复杂度下能够跑的很快。