题解：P12147 【MX-X11-T1】「蓬莱人形 Round 1」仅此而已，就已经足够了

· · 题解

偶遇数学题拼尽全力无法战胜，怎么会是呢。

调了三天甚至两天，耶耶耶。

观察到增加一个 2^k 变化的位数有限，而异或统计答案只关注于变化的这些位，于是考虑按位统计答案。

注意到 2^k 的贡献次数为 n+1，先算掉。

注意到第 i 位产生贡献时，必然满足从第 k 位到 i-1 位必须全部为 1。

于是不妨 n \gets n+2^k，那么此时我们只需要统计第 i 位是 1 而从 k 到 i-1 位全为 0 的出现次数，这是好做的。

然后贡献大小就是 2^{i+1}-2^{k+1}。

直接写就行，请务必保持头脑清楚以及明确每一行的作用！

#include<bits/stdc++.h>
#define int long long
using namespace std;
void solve(){
    int n,k;
    cin>>n>>k;
    int ans=(1<<k)*(n+1);
    n+=(1<<k);
    // cout<<n<<"! ";
    for(int i=1<<(k+1);i<=n;i*=2){
        // cout<<ans<<' ';
        int f=n/(i<<1);
        int c=min(1ll<<k,n%i+1);
        int sum=f*(1<<k);
        ans+=sum*i*2-sum*(1<<(k+1));
        // cout<<c<<' ';
        if(n&i)ans+=i*c*2-c*(1<<(k+1));
    }
    cout<<ans<<'\n';
}
/*
  0
  1
 10
 11
100

101
110
*/
signed main(){
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}
/*
72
272
50
18

4
9 2
17 3 
8 1 
4 1 
*/