Luobuyu's Blog

0%

D.小美的区间异或和

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 2.6k 阅读时长 ≈ 2 分钟
美团笔试题，需要知道如何求解异或和，需要按位拆分。

D.小美的区间异或和

题目描述：

小美定义一个数组的权值为：数组中任选两个数的异或之和。例如，数组 $[2,1,3]$ 的权值为： $(2 \oplus 1)+(2 \oplus 3)+(1 \oplus 3)=3+1+2=6$ 。
小美拿到了一个数组，她想知道该数组的所有连续子数组的权值和是多少？答案对 $10^9 + 7$ 取模。

数据范围：

$1\le n \le 10^5;1\le a_i \le 10^9$

题解：

首先如何计算一个数组的权值？需要用到按位拆分的思想。

异或出来的值只与当前位的 $0$ 和 $1$ 的数目有关，因为只有 $0$ 和 $1$ 异或才能得到 $1$ ，才会对答案有贡献。对于一个集合，按位拆分之后，假设当前第 $i$ (从低位到高位) 位 $0$ 的个数为 $cnt[i][0]$ ， $1$ 的个数为 $cnt[i][1]$ ，那么当前位对答案的贡献就为 $cnt[i][0] \times cnt[i][1] \times (1 << i)$ ，因为当前位的权重为 $2^i = (1 << i)$ 。那么整个集合的权重就为 $\sum_{i = 0}^{31} cnt[i][0] \times cnt[i][1] \times 2^i $ 。

假设往集合里面加入一个新的元素 $nums[i]$ ，新数组的权值和（注意不是所有的连续子数组）如何计算呢？

也是按位拆分，首先计算原集合 $nums[1,\cdots,i-1]$ 中每个位上有多少个 $1$ ，有多少个 $0$ ，注意是所有的 $nums[1],\cdots,nums[i-1]$ 累加的，也就是按位拆分之后的前缀和。然后将 $nums[i]$ 也拆分，从高位到低位或者从低到高，如果 $nums[i]$ 的第 $j$ 位为 $1$ ，那么就加上 $cnt0 \times 2^j$ ，否则加上 $cnt1\times 2^j$ 。因为只有 $nums[i]$ 的第 $j$ 位与前面的不同时才会产生贡献。

以后遇到类似的问题也可以这样做。跟异或和有关的都可以拆分，按位做。

该问题需要动态规划和加权策略。

然后该题目需要用到动态规划，设 $dp[i]$ 为以 $nums[i]$ 结尾的所有连续子数组的权值和，那么当加入一个新的数 $nums[i]$ 时：

首先子数组 $nums[1,\cdots,i]$ 中增加了 $nums[1] \oplus nums[i],\cdots, nums[i-1] \oplus nums[i]$

子数组 $nums[2,\cdots,i]$ 中增加了 $nums[2] \oplus nums[i],\cdots,nums[i-1]\oplus nums[i]$ 。

$\cdots \cdots$

可以看出，加入 $nums[i]$ 之后，总的权值增加了 $1\times nums[1] \oplus nums[i] + 2\times nums[2] \oplus nums[i] + \cdots + (i - 1)\times nums[i-1] \oplus nums[i]$ 。首先通过上面可以知道，在加入 $nums[i]$ 之后，增加的是 $nums[1] \oplus nums[i] + nums[2] \oplus nums[i] + \cdots + nums[i-1] \oplus nums[i]$ ，新数组的（不是所有连续子数组）权值可以通过每个位上 $0,1$ 的数目来计算。连续子数组的与之相比，每一项多了一个权重。可以把这个权重放到每一位上，比如在统计 $nums[1]$ 各个位上 $0$ 和 $1$ 的数目时，对数目乘以权重。也就是 $i \times cnt[0/1]$ 。然后再求前缀和。求出前缀和之后，使用 $dp$ ，求以 $nums[i]$ 结尾的所有连续子数组的权值和。最后把所有的 $dp[i]$ 求和即可。

其中 $preSum$ :

代码：

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e5 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
ll a[maxn];
ll sum[maxn][32][2];
ll dp[maxn];
void count(int i, int num)
{
    for (int j = 31; j >= 0; --j)
    {
        if ((num >> j) & 1)
            sum[i][j][1] = 1 * i;
        else
            sum[i][j][0] = 1 * i;
    }
}
int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    read(n);
    for (int i = 1; i <= n; ++i)
    {
        read(a[i]);
        count(i, a[i]);
        for (int j = 0; j < 32; ++j)
        {
            sum[i][j][0] = (sum[i][j][0] + sum[i - 1][j][0]) % mod;
            sum[i][j][1] = (sum[i][j][1] + sum[i - 1][j][1]) % mod;
        }
    }
    ll ans = 0;
    for (int i = 2; i <= n; ++i)
    {
        ll tmp = 0;
        for (int j = 31; j >= 0; --j)
        {
            tmp = (tmp + 1ll * sum[i - 1][j][!((a[i] >> j) & 1)] * (1 << j)) % mod;
        }
        dp[i] = (dp[i - 1] + tmp) % mod;
        ans = (ans + dp[i]) % mod;
    }
    cout << ans << endl;
    return 0;
}