Luobuyu's Blog

0%

2527. 查询数组异或美丽值

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 1.4k 阅读时长 ≈ 1 分钟
思维题，可以提取公式。

2527.查询数组异或美丽值

题目描述：

给你一个下标从 0 开始的整数数组 nums 。

三个下标 i ，j 和 k 的 有效值 定义为 ((nums[i] | nums[j]) & nums[k]) 。

一个数组的 异或美丽值 是数组中所有满足 0 <= i, j, k < n 的三元组 (i, j, k) 的 有效值 的异或结果。

请你返回 nums 的异或美丽值。

注意：

  • val1 | val2 是 val1 和 val2 的按位或。
  • val1 & val2 是 val1 和 val2 的按位与。

数据范围：

$1\le nums.len \le 10^5, 1\le nums[i] \le 10^9$

题解：

统计每一位上 $0$ 的个数 $cnt0$ 和 $1$ 的个数 $cnt1$ 。

然后对每一位分别考虑贡献是多少。因为可以重复选取，每一个数可以被选取多次。而且是每一位上的异或值，因此只需要计算每一位上最终 $1$ 的个数是奇数还是偶数。如果一个三元组该位为 $1$ ，那么 $nums[k]$ 必为 $1$ ， $nums[i],nums[j]$ 不能同时为 $0$ ，因此种类数为 $cnt1 \times (cnt01 cnt01 - cnt0 cnt0)$ ，即减去同时为 $0$ 的。

化简之后为 $cnt1 \times ((cnt1 + cnt0 + cnt0) \times cnt1) = cnt1 \times cnt1 \times (2\times cnt0 + cnt1) = 2\times cnt0 \times cnt1^2 + cnt1^3$

由于 $2\times cnt0 \times cnt1^2$ 一定为偶数，因此奇偶性只与 $cnt1^3$ 有关，只与 $cnt1$ 有关。

也就是只与最终每一位上的 $1$ 的奇偶有关，这就是直接异或了。

代码：

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
31
32
33
34
35
36
37
38
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const static int INF = 0x3f3f3f3f;
    const static long long INF_LL = 0x3f3f3f3f3f3f3f3f;
    const static long long mod = 1e9 + 7;
    int xorBeauty(vector<int> &nums)
    {
        int n = nums.size();
        vector<int> cnt0(32);
        vector<int> cnt1(32);
        for (int i = 0; i < n; ++i)
        {
            for (int j = 31; j >= 0; --j)
            {
                if ((nums[i] >> j) & 1)
                    cnt1[j]++;
                else
                    cnt0[j]++;
            }
        }
        long long ans = 0;
        for (int i = 31; i >= 0; --i)
        {
            ans += 1ll * (1ll * (2 * cnt0[i] + cnt1[i]) * cnt1[i] * cnt1[i] % 2) * (1 << i);
        }
        return ans;
    }
};