Description

小呆开始研究集合论了, 他提出了关于一个数集四个问题:

  1. 子集的异或和的算术和.
  2. 子集的异或和的异或和.
  3. 子集的算术和的算术和.
  4. 子集的算术和的异或和.

目前为止, 小呆已经解决了前三个问题, 还剩下最后一个问题还没有解决, 他决定把 这个问题交给你, 未来的集训队队员来实现.

Input

第一行, 一个整数 n.

第二行, n 个正整数, 表示 a1, a2...... ．,.

Output

一行, 包含一个整数, 表示所有子集和的异或和.

Sample Input

2
1 3

Sample Output

6

Sample Explanation

6=1 异或 3 异或 (1+3)

Data Range

\(a_i \gt 0\),\(1 \lt n \lt 1000\),\(\sum a_i \leq 2000000\).

另外, 不保证集合中的数满足互异性, 即有可能出现 Ai=Aj 且 i 不等于 J

Solution

一道玄学题...... 前面的三种情况都比较好想:

算术和的算术和: 考虑针对每个数选与不选的情况, 那么每一个数被选的种数有 \(2^{n-1}\), 而且不被选中的种数有 \(2^{n-1}\) 个. 固然最后的答案为:

\[\sum_{i=1}^{n} a_i \cdot 2^{n-1}\]

异或和的异或和: 考虑每一位被选的情况有 \(2^{n-1}\) 次, 不被选的情况也有 \(2^{n-1}\) 次, 并且 \(2^{n-1}\) 是一个偶数, 所以完全亦或之后结果的所有位上都是 \(0\), 固然异或和的异或和总是 \(0\).

异或和的算数和: 由于亦或操作在每一位上完全独立, 所以我们可以转化成一个 0-1 问题. 考虑在某一位上一共有 \(m\) 个 \(1\),\(n - m\) 个 \(0\), 那么最后这一位所能构成的子集的个数有 \(2^n\) 个, 其中有一部分的异或和是 \(1\), 其余的是 \(0\). 注意到所有构成异或和 为 \(1\) 的子集中都有奇数个 \(1\), 而 \(0\) 的数量没有关系. 自然问题就转化成为了从 \(n-m\) 个数中选出奇数个数和从 \(m\) 个数中选出任意多个数 (考虑数与数之间的差异) 的方法数. 由于本题没有具体涉及这个方面, 我再此就不给出具体的结果了.

最后是算数和的异或和. 考虑相同的两组算数和 (出自不同的子集), 它们无论接下来如何选择, 最后它们的亦或和总是 \(0\) (因为被湮灭掉了). 这样一来, 我们只需要每一次维护 一下这个和, 然后把不应该出现的东西湮灭掉就可以了. 时间复杂度是 O (max n), 有可能超时. 然而用一个神奇的 bitset 维护一下就可以省下整整一个 \(64\) 的常数, 保证 在时限内做完.

bitset, 处理高精位运算的有力工具 (雾)

另外 bitset 有一点玄学. 假如将下面代码中的 int x 从全局变量中移到局部变量里, 也就是说, 加在 scanf("%d", &x); 之前. 理论上这不会造成任何影响, 在本机上也不会, 但是交到耒阳上就会不停 WA. 为了这个我提交了差不多 16 次才找到这个问题. 另外豫先 把数据读到 int arr[maxn] 里, 再预处理这样也是不行的, 虽然逻辑上没有任何错误, 在本地测完也是正确的, 但是都会挂在耒阳上.

我强烈要求 BZOJ 的 Maintainer 给一个说法!! ! (当然也有可能是玄学 STL)

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <bitset>

using namespace std;
typedef long long lli;
const int maxn = 2001000;

int n, x, sum, res;
bitset<maxn> dp;

int main(int argc, char** argv)
{
    scanf("%d", &n);
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &x);
        sum += x;
        dp ^= (dp << x);
    }
    for (int i = 1; i <= sum; i++)
        if (dp[i])
            res ^= i;
    printf("%d", res);
    return 0;
}