这题评黄？

题意简述

定义 \(f(x)=x\oplus(x+2^k)\)。给出 \(n\)，求 \(f(0)+f(1)+f(2)+\cdots+f(n)\)。\(T\) 组询问，每组有不同的 \(n\) 和 \(k\)。\(1 \le T\le 10^5\)，\(0 \le n < 2^{29}\)，\(0 \le k \le 29\)。

思路

由于 \(T\) 较大，考虑 \(O(1)\) 或 \(O(\log n)\) 求法。先打表找规律。因题目有特殊性质 \(k=0\)，考虑先打 \(k=0\) 时 \(f(0)\) 到 \(f(n)\) 的值。由于涉及位运算，考虑同时观察二进制。打表得到
\[ f(0)=1=(1)_2\\ f(1)=3=(11)_2\\ f(2)=1=(1)_2\\ f(3)=7=(111)_2\\ f(4)=1=(1)_2\\ f(5)=3=(11)_2\\ f(6)=1=(1)_2\\ \cdots \] 观察到一种对称性：\(f(0)\) 和 \(f(2)\) 关于 \(f(1)\) 对称，然后将这 \(3\) 个数视为一个整块，则 \(f(0)\) 到 \(f(2)\) 的部分和 \(f(4)\) 到 \(f(6)\) 的部分关于 \(f(3)\) 对称。同理，\(f(0)\) 到 \(f(6)\) 的部分还能继续对称下去。为了方便，我们把最短的块 \(f(0)=1\) 记作 \(K_1\)，称为 \(1\) 阶块，\(K_n\) 的长度记为 \(len_n\)，\(K_n\) 内所有元素之和为 \(sum_n\)。则 \(K_2\) 应当包含 \(f(0)\)，\(f(1)\)，\(f(2)\)。以此类推。
接下来，尝试将规律推广到 \(k>0\) 的情况。
打 \(k=1\) 的表，得
\[ f(0)=(10)_2\\ f(1)=(10)_2\\ f(2)=(110)_2\\ f(3)=(110)_2\\ f(4)=(10)_2\\ f(5)=(10)_2\\ f(6)=(1110)_2\\ f(7)=(1110)_2\\ \cdots \] 我们发现，\(len_1\) 变为了 \(2^1\)。而 \(K_1\) 中的值变为了 \((10)_2\)，也就是 \(2^1\)。继续打出 \(k=2\) 和 \(k=3\) 时的表，发现如下规律：
\(len_1\) 为 \(2^k\)，\(K_1\) 中的元素的值为 \(2^k\)。

实现

考虑分治。
考虑从 \(K_x\) 推得 \(K_{x+1}\)，我们发现，\(K_{x+1}\) 应分为 \(3\) 部分，\(K_x\) 作为左右两部分，\(2^k\) 个 \(2^{x+1}-1\) 左移 \(k\) 位作为中间部分。容易发现 \(len_{x+1}=2 \times len_x+2^k\)。
反之，从 \(K_{x+1}\) 推得 \(K_x\)，有 \(len_{x}=\dfrac{len_{x+1}-2^k}{2}\)。
由于 \(k>0\) 时的 \(sum_n\) 都可从 \(k=0\) 时的 \(sum_n\) 通过位运算 \(O(1)\) 求出，考虑预处理出 \(k=0\) 时的 \(sum_1\) 到 \(sum_k\)，之所以只处理到 \(sum_k\)，是因为 \(len_k\) 刚好略大于 \(\max(n)\)，即 \(2^{29}\)，已经可以覆盖所有 \(f(x)\)。
其他实现细节详见代码注释。

code

这里的递归过程很像线段树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<iostream>
#define int long long
using namespace std;
const int MAXN=536870911;
int t,n,k;//同原题
int len;//中间部分长度，同时也是最小块长
int cnt;//阶数
int sum[40];//k=0时的块内和
int lensum;//大于n的最小块长
long long solve(int u,int l,int r,int x,int y){
	if(x>r||y<l)
		return 0;//超出范围，直接退出
	int len1=(r-l+1-len)/2;//左右子块长度
	long long res=0;
	if(y-x+1<=len)//查询区间已小于或等于最小块长
		return (1ll<<k)*(y-x+1);//(sum[1]<<k)*查询区间长
	if(x<=l&&y>=r)//查询区间完全覆盖当前区间
		return (sum[u]<<k)*len;
	res+=solve(u-1,l,l+len1-1,x,y);//左子块递归
	int l1=max(x,l+len1),r1=min(y,l+len1+len-1);//这里要让中间部分与查询部分取交集
	res+=max(0ll,(r1-l1+1))*(((1ll<<u)-1)<<k);
	res+=solve(u-1,l+len1+len,r,x,y);//右子块递归
	return res;
}
void get_length(){
	lensum=len;
	while(lensum<=n){
		lensum<<=1;//左右子块长度相等，直接乘2
		lensum+=len;//中间部分
		cnt++;
	}
	return;
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>t;
	sum[1]=1;//k=0时，f(0)=1
	for(int i=2;i<=30;i++){
		sum[i]=sum[i-1]<<1;//左右子块和相等，直接乘2
		sum[i]+=(1ll<<i)-1;//中间部分
	}
	while(t--){
		cin>>n>>k;
		len=1ll<<k;//中间部分长度
		cnt=1;//阶数
		get_length();//获取覆盖0到n的最小块长
		cout<<solve(cnt,0,lensum,0,n)<<'\n';
	}
	return 0;
}
时间复杂度 \(O(T\log n)\)。

证明

对于 \(f(x)\) 的值的二进制 \(k\) 位及以下均为 \(0\) 很显然，因为 \(2^k\) 最低影响到第 \(k+1\) 位。而 \(x\) 必须增长 \(2^k\) 才能令第 \(k+1\) 位更改一次，所以可得 \(len_1=2^k\) 和中间块长等于 \(len_1\)。由此我们还可得，\(f(x)\) 的值发生更改（在 \(x\) 每次加 \(1\) 时）当且仅当 \(x\) 的 \(k+1\) 位的值更改。如：令 \(k=1\)，则 \(f((1)_2)\) 到 \(f((10)_2)\)，第 \(2\) 位发生更改，\(f(x)\) 的值由 \((10)_2\) 变为 \((110)_2\)。接下来考虑高位。我们发现，\(k+1\) 位以上，连续的一串 \(1\) 会使答案形成“若干个连续 \(1\)”的结构。而高位连续的 \(n\) 个 \(1\) 的变换恰有 \(2^{n-1}\times 2^k\) 的周期性（乘 \(2^k\) 是因为要考虑低位）。可以联想一个二进制数的不断加 \(1\) 操作，观察最低位连续 \(1\) 的变化。以上两部分结合即得我们观察到的规律。
这个方法被喷飞了我不能理解，我感觉很容易注意到规律而且代码实现没有那么难啦……

友链：大佬 yonghu10010 的题解，与本题解使用相同思路，但实现方式略有出入。