P12177 [蓝桥杯 2025 省 Python B] 异或和

题目描述

小蓝有 $n$ 个数 $a_i$，他想知道这 $n$ 个数中的所有数对下标的差值乘上它们的异或之后，得到的结果的和是多少。

也就是说，小蓝想要得到

$$\sum _{i=1}^n\sum _{j=i+1}^n(a_i\oplus a_j)\times (j-i)$$

的值，其中 $\oplus$ 表示按位异或。

输入格式

输入的第一行包含一个正整数 $n$。

第二行包含 $n$ 个正整数 $a_1,a_2,\cdots ,a_n$，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

输入输出样例 #1

输入 #1

3
1 2 3

输出 #1

8

输入输出样例 #2

输入 #2

4
9 8 7 6

输出 #2

118

说明/提示

评测用例规模与约定

• 对于 $40\%$ 的评测用例，$n\le 5000$；
• 对于所有评测用例，$1\le n\le 10^5$，$1\le a_i\le 2^{20}$。

C++实现

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
int a[N], n;
ll b[30][2], cnt[30][2];
void print(ll x)
{
    if(x < 10) putchar(x + '0');
    else print(x / 10) ,putchar(x % 10 + '0');
}
int main()
{
    cin >> n;
    for(int i = 1;i <= n;++i) scanf("%d", &a[i]);
    ll ans = 0;
    for(int i = 1;i <= n;++i)
    {
        for(int j = 0;j <= 20;++j)
        {
            ans += (1ll << j) * b[j][!((a[i] >> j) & 1)];
            b[j][0] += cnt[j][0], b[j][1] += cnt[j][1];
            b[j][(a[i] >> j) & 1]++;
            cnt[j][(a[i] >> j) & 1]++;
        }
    }
    print(ans);
    return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容