DDOSvoid's Blog

2021 CCPC 新疆省赛 H xor

发表于 更新于 分类于
本文字数： 1k 阅读时长 ≈ 1 分钟

题目描述

https://ac.nowcoder.com/acm/contest/22754/H

简要题意：给定一个长度为 $n$ 的序列 $a_i$，求 $\sum_{i=1}^n\sum_{j=1}^n(a_i\oplus a_j)^2$，$\oplus$ 代表异或运算

$n\le 5\times 10^5$

Solution

我们考虑平方分解：$(\sum_{i=1}^na_i)^2=\sum_{i=1}^n\sum_{j=1}^na_ia_j$

那么对于 $(a_i\oplus a_j)^2$，我们可以看做是若干个二进制的和的平方，那么我们现在只需要枚举两个二进制位进行计算即可

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

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
#include <iostream>
#define maxn 50010
#define ll long long
using namespace std;

const int p = 1000000007;

int n, a[maxn], cnt[30][30][2][2];
int base[60];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    base[0] = 1; for (int i = 1; i < 60; ++i) base[i] = base[i - 1] * 2ll % p; 
    for (int i = 1; i <= n; ++i) 
        for (int s = 0; s < 30; ++s)
            for (int t = 0; t < 30; ++t)
                cnt[s][t][a[i] >> s & 1][a[i] >> t & 1]++;
    int ans = 0; 
    for (int i = 0; i < 30; ++i)
        for (int j = 0; j < 30; ++j)
            for (int s = 0; s < 2; ++s)
                for (int t = 0; t < 2; ++t)
                    ans = (ans + 1ll * base[i + j] * cnt[i][j][s][t] % p * cnt[i][j][s ^ 1][t ^ 1]) % p;
    cout << ans << "\n";
}