自动搬运

查看原文

来自洛谷，原作者为

	_FastFT2013 抽象之神||2024csp J:275 S:220

搬运于2025-08-24 23:13:08，当前版本为作者最后更新于2025-04-12 20:29:47，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

本蒟蒻考试的时候也是只打了 210pts，直接场切。

Solution:

我们考虑将 $f(x)$ 进行改变：

由于 $⊕$ 运算属于二进制运算，所以此处 $x$ 都用的是二进制。

我们可以将 $x$ 的二进制描述成以下方式：

$(x)_2 =$ 一些乱七八糟的东西 $+$ 一个 $0$ $+$ $t$ 个连续的 $1$（结尾一定是二进制第 $k$ 位，$t$ 可以为 $0$）$+$ 一些乱七八糟的东西。

这里的二进制第几位是从右往左数的，二进制串最右边才是 $2^0$。

我们把第一个“一些乱七八糟的东西” 写做二进制数 $x_ 1$，把第二个“一些乱七八糟的东西” 写作二进制数 $x_2$。

注意：“一些乱七八糟的东西” 是可以没有的。

例如样例：

$3$ $0$

$(3)_2 = 101 =$ $x_1$（$1$）$+$ 一个 $0$ $+$ 一个连续的 $1$ $+$ $x_2$（没有）。

那么把一个二进制拆成这样有什么用呢？

这就要提到 $⊕$ 的计算方式了，二进制位相同得 $0$，不同得 $1$。

接下来我们将 $f(x)$ 进行变式，通过对每部分进行讨论得出：

原式：$f(x) = x ⊕ (x + 2^k)$。

对于 $x_2$ 的部分，加法只会对第 $k$ 位以上的数字作影响，所以 $x_2$ 没有动，异或值为 $0$。

对于（一个 $0$ $+$ $t$ 个连续的 $1$）这部分，加法表示在第 $k$ 位加 $1$，相当于在这部分的最右边那一位加 $1$，则整体会变为（一个 $1$ $+$ $t$ 个连续的 $0$），异或值为（连续的 $t+1$ 个 $1$）。

对于 $x_1$ 的部分，由于用一个 $0$ 来隔开加法进位了，所以不会对当前部分产生影响，不会发生改变，异或值为 $0$。

所以说我们可以将 $f(x)$ 的二进制写成这样：

$f(x) =$ 以第 $k$ 位结尾的连续的 $t+1$ 个 $1$。

那这根我们算答案有什么关系呢？

我们发现，实际上可以枚举 $t$，算出二进制中有一个 $0$ $+$ 从第 $k$ 为结尾连续 $t$ 个 $1$，并且满足这个数小于等于 $n$ 的方案数，将方案数乘上当前贡献就可以得出当前结果。

我们现在假设要满足以上条件，并且给出了 $t$。

首先（一个 $0$ $+$ 从第 $k$ 为结尾连续 $t$ 个 $1$）可以使用公式推导出来：

一个 $0$ $+$ 连续 $t$ 个 $1$ $= 2^t - 1$。

上述条件加上以第 $k$ 结尾 $=(2^t - 1) \times 2^k$。

然后我们要求出满足条件的最大的数，

这个不能使用公式进行推导，我们可以从高位枚举到低位，每次查看能不能把这个位变为 $1$ 并且满足条件，若能，就把这个位变为 $1$。

提示：在第 $k$ 位到第 $k+t$ 位不能改，应为这是（一个 $0$ $+$ 从第 $k$ 为结尾连续 $t$ 个 $1$）。

设这个满足条件的最大数为 $p$。

ll p=((1ll<<t)-1)<<k;
if(p>n)continue;//此处判断有没有方案
for(int j=30;j>=0;j--){//高位枚举到低位
	if(j>=k&&j<=k+t)continue;
	if(p+(1ll<<j)<=n){
		p+=(1ll<<j);
	}
}

现在我们求出来了，那怎么做呢？

我们考虑 $p$ 的 $x_1$ 和 $x_2$，将 $a$ 和 $b$ 设为这两个值（此处只是为了简便）。

公式推导 $a$ 和 $b$：

$a$ 为 $p$ 的二进制去掉后 $t + k + 1$ 位的值，

及 $a = \lfloor \frac{p}{2^{t+k+1}} \rfloor$。

$b$ 为 $p$ 的二进制后 $k-1$ 位，

及 $b = p \bmod (k-1)$。

ll a=p>>(i+k+t),b=p%(1ll<<k);

我们将满足条件的数的情况分为两种：

第一种：满足条件的数的 $x_1 < a$，则满足条件的数的 $x_2$ 可以为任何前 $k-1$ 位的二进制数（想不出来的可以画图理解）。

则方案数为：

（$x_1 < a$）的方案 $= a + 1 - 1 = a$（相当于减去了 $x_1 = a$ 的情况，增加了 $x_1 = 0$ 的情况）。

（$x_2$ 可以为任何 $k-1$ 位的二进制数）的方案 $= 2^k$（相当于每一位有 $2$ 种情况，从共有 $k$ 位（$0$ 这一位要记录进去））。

第一种的总方案 $=$（（$x_1 < a$）的方案）$\times$（（$x_2$ 可以为任何 $k-1$ 位的二进制数）的方案）$= a \times 2^k$ 设其为 $q_1$。

ll q1=a<<k;

第二种：满足条件的数的 $x_1 = a$，则满足条件的数的 $x_2$ 可以为任何 $\le b$ 位的二进制数（想不出来的可以画图理解）。

则方案数为：

（$x_1 = a$） 的方案 $= 1$。

（$x_2$ 可以为任何 $\le b$ 位的二进制数）的方案 $= b + 1$（加的 $1$ 是 $x_2 = 0$ 的情况）。

第二种的总方案 $=$（（$x_1 = a$）的方案）$\times$（（$x_2$ 可以为任何 $\le b$ 位的二进制数）的方案）$= 1 \times (b + 1)$ 设其为 $q_2$。

ll q2=b+1;

所以总的方案数为 $q_1 + q_2$。

答案为之前推出来的（以第 $k$ 位结尾的连续的 $t+1$ 个 $1$）$= 2^{t+1} - 1$。

当前总答案为 $(q_1 + q_2) \times (2^{t+1} - 1)$。

$t$ 这个数只需要枚举就好了。

单次时间复杂度 $O(\log^2 n)$。

Code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
void solve(){
	ll n,k;
	cin>>n>>k;
	ll sum=0;
	for(int i=0;i<=30;i++){//这里的i就是t
		ll p=((1ll<<i)-1)<<k;
		if(p>n)continue;
		for(int j=30;j>=0;j--){
			if(j>=k&&j<=k+i)continue;
			if(p+(1ll<<j)<=n){
				p+=(1ll<<j);
			}
		}
        ll a=p>>(i+k+1),b=p%(1ll<<k);
		ll q1=a<<k;
		ll q2=b+1;
		sum+=(q1+q2)*(((1ll<<(i+1))-1)<<k);
	}
	cout<<sum<<"\n";
}
int main(){
	int t;
	cin>>t;
	while(t--)solve();
    return 0;
}