牛客网 - SHTMYCBDFTT(异或)

题目链接:https://ac.nowcoder.com/acm/contest/393/B
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld

题目描述

注意本题有模数
给定一个长度为 n 的序列{a}，求：
max 1≤i≤j≤n{(ai⊕ai+1⊕⋯⊕aj)+(ai+ai+1+⋯+aj)}mod100000007
其中 ⊕ 表示异或

输入描述:

第一行一个整数 n 。
第二行 n 个整数，表示 ai。

输出描述:

一行一个整数 ans，表示答案。

输入

3
1 2 3

输出

6

说明

我们 显然需要将所有的数字都选上，此时 ans=(1⊕2⊕3)+1+2+3=6.

备注:

对于所有的数据，保证 1≤n≤3×10^5,0≤ai<2^20。
样例：想不到吧，你的做法至少能过样例！

解题思路

我们很容易知道a^b>=a-b,即a^b+b>=a。当我们遇到一个数b的时候，如果我们不选b的话，到最后就加上一个ans2，如果选的话，我们就会加上ans2^b+b,由上可知ans2^b+b>=ans2。说明ans2=ans2^b之后有可能会使ans2变小，但是ans1会多加上一个b，所以只要遇到一个数就要把它全加上。

#include <stdio.h>
int main() {
    int n, m;
    long long ans1, ans2;
    while (~scanf("%d", &n)) {
        ans1 = ans2 = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d", &m);
            ans1 += 1ll * m;
            ans2 ^= 1ll * m;
        }
        printf("%lld\n", (ans1 + ans2) % 100000007);
    }
    return 0;
}