题解：P12147 【MX-X11-T1】「蓬莱人形 Round 1」仅此而已，就已经足够了
ACFT
·
·
题解
本蒟蒻考试的时候也是只打了 210pts，直接场切。
Update2025/11/14:发现一处数学公式推错了，进行了修改
Solution:
我们考虑将 f(x) 进行改变：
由于 ⊕ 运算属于二进制运算，所以此处 x 都用的是二进制。
我们可以将 x 的二进制描述成以下方式：
这里的二进制第几位是从右往左数的，二进制串最右边才是 $2^0$。
我们把第一个“一些乱七八糟的东西” 写做二进制数 $x_
1$，把第二个“一些乱七八糟的东西” 写作二进制数 $x_2$。
注意：“一些乱七八糟的东西” 是可以没有的。
例如样例：
$3$ $0
那么把一个二进制拆成这样有什么用呢？
这就要提到 $⊕$ 的计算方式了，二进制位相同得 $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$。
```c++
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)$。
```c++
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$。
```c++
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$。
```c++
ll q2=b+1;
```
所以总的方案数为 $q_1 + q_2$。
答案为之前推出来的（以第 $k$ 位结尾的连续的 $t+1$ 个 $1$）$= (2^{t+1} - 1)\times 2^k$。
当前总答案为 $(q_1 + q_2) \times (2^{t+1} - 1) \times 2^k$。
$t$ 这个数只需要枚举就好了。
单次时间复杂度 $O(\log^2 n)$。
# Code:
```c++
#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;
}
```