Description

小 Q 学习位运算时发现了异或的秘密.

小 Q 是一个热爱学习的人, 他经常去维基百科 http://en.wikipedia.org/wiki/Main_Page 学习计算机科学.

就在刚才, 小 Q 认真地学习了一系列位运算符 http://en.wikipedia.org/wiki/Bitwise_operation, 其中按位异或的运算符 xor 对他影响很大. 按位异或的运算符是双目运算符. 按位异或具有 交换律, 即 \(\ \text{xor}\ j = j\ \text{xor}\ i\).

他发现, 按位异或可以理解成被运算的数字的二进制位对应位如果相同, 则结果的该位置为 \(0\), 否则为 \(1\), 例如 \((01)_2\ \text{xor}\ (10)_2 = (11)_{2}\).

他还发现, 按位异或可以理解成数字的每个二进制位进行了不进位的加法, 例如 $(11) _2   (11) 2=(00) {2}.

于是他想到了两个关于异或的问题, 这两个问题基于一个给定的非负整数序列 \(A_1, A_2, \ldots, A_n\), 其中 \(n\) 是该序列的长度.

第一个问题是, 如果用 \(f(i, j)\) 表示 \(A_i\ \text{xor}\ A_{i+1}\ \text{xor}\ \ldots\ \text{xor}\ A_j\), 则任意的 \(1 \leq i \leq j \leq n\) 的 \(f(i, j)\) 相加是多少.

第二个问题是, 如果用 \(g(i, j)\) 表示 \(A_i + A_{i+1} + \ldots + A_j\), 则任意的 \(1 \leq i \leq j \leq n\) 的 \(g(i, j)\) 异或在一起是多少.

比如说, 对于序列 \(\{1, 2\}\), 所有的 \(f()\) 是 \(\{1, 2, 1\ \text{xor}\ 2\}\), 加起来是 \(6\); 所有的 \(g()\) 是 \(\{1, 2, 1 + 2\}\), 异或起来是 \(0\).

他觉得这两个问题都非常的有趣, 所以他找到了你, 希望你能快速解决这两个问题, 其中 第一个问题的答案可能很大, 你只需要输出它对 \(998244353\) (一个质数) 取模的值即可.

Input

第一行一个正整数 \(n\), 表示序列的长度.

第二行 \(n\) 个非负整数 \(A_1, A_2, \ldots, A_n\), 表示这个序列.

Output

两个整数, 表示两个问题的答案, 空格隔开, 其中第一个问题的答案要对 \(998244353\) 取模.

Sample Input

2
1 2

Sample Output

6 0

Data Range

100% 的数据满足:\(n \leq 10^5, A_i \leq 10^6\).

Explanation

传送门:http://blog.csdn.net/skywalkert/article/details/45401245

我是蒟蒻只会写树状数组不会做题;

我是蒟蒻连树状数组都能写错 change();

我是蒟蒻目测挂菜 QwQ

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long lli;
const int maxn = 100100;
const int modr = 998244353;

class BinaryIndexedTree
{
public:
    int dat[maxn], n;
    void change(int x)
    {
        for (; x <= n; x += ~x & (x + 1))
            dat[x] ^= 1;
        return ;
    }
    int query(int x)
    {
        int res = 0;
        for (; x >= 0; x -= ~x & (x + 1))
            res ^= dat[x];
        return res;
    }
    void init(int n)
    {
        this->n = n;
        memset(dat, 0, sizeof(dat));
        return ;
    }
} bit;

int n, arr[maxn];
int xsum[maxn]; // Sum of logic xor
lli ssum[maxn]; // Sum of arithmetic addition
lli p[maxn];

template <typename _T1, typename _T2>
void remod(_T1& a, _T2 b) {
    lli c = (lli)a + (lli)b;
    while (c > modr)
        c -= modr;
    a = c; return ;
}

template <typename _T>
inline int get_digit(_T a, int b) {
    return (a >> b) & 1;
}

int find(lli val)
{
    int l = -1, r = n;
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (p[mid] <= val) l = mid;
        else r = mid - 1;
    }
    return l;
}

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &arr[i]);
        xsum[i] = xsum[i-1] ^ arr[i];
        ssum[i] = ssum[i-1] + arr[i];
    }
    // Subtask #1, calculate the sum of xor sums
    int res1 = 0;
    for (int k = 0; k < 30; k++) { // For each digit
        int cnt[2] = {}, tmp = 0;
        // For each item in items, calculate sums
        for (int i = 0; i <= n; i++) {
            remod(tmp, cnt[get_digit(xsum[i], k) ^ 1]);
            cnt[get_digit(xsum[i], k)] += 1;
        }
        // Add temporary point to result
        remod(res1, (1ll << k) * tmp % modr);
    }
    // Subtask #2, calculate the xor sum of sums
    lli res2 = 0;
    for (lli k = 0; (1ll << k) <= ssum[n]; k++) { // For each digit (large!)
        int tmp = 0;
        // Get certain digits.
        for (int i = 0; i <= n; i++)
            p[i] = ssum[i] & ((1ll << (k+1)) - 1);
        sort(p, p + n + 1);
        bit.init(n);
        for (int i = 0; i <= n; i++) {
            lli cur = ssum[i] & ((1ll << (k+1)) - 1);
            bit.change(find(cur));
            tmp ^= bit.query(find(cur - (1ll << k)))
                ^  bit.query(find(cur + (1ll << k)))
                ^  bit.query(find(cur));
        }
        if (tmp)
            res2 |= 1ll << k;
    }
    // Gather information
    printf("%d %lld\n", res1, res2);
    return 0;
}