#P4017. 小Q的无敌异或

    ID: 3218 传统题 3000ms 128MiB 尝试: 925 已通过: 196 难度: 7 上传者: 标签>CF2200提高异或前缀和一维前缀和按位独立贡献离散化树状数组鸣谢佚名上传

小Q的无敌异或

题目描述

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

小Q是一个热爱学习的人,他经常去维基百科学习计算机科学。

就在刚才,小Q认真地学习了一系列位运算符,其中按位异或的 运算符 ⊕\oplus 对他影响很大。按位异或的运算符是双目运算符。按位异或具有交换律,即 i⊕j=j⊕ii \oplus j = j \oplus i。

他发现,按位异或可以理解成被运算的数字的二进制位对应位如果相同,则结果的该位置为 00,否则为 11,例如 1(01)⊕2(10)=3(11)1(01) \oplus 2(10) = 3(11)。 他还发现,按位异或可以理解成数字的每个二进制位进行了不进位的加法,例如 3(11)⊕3(11)=0(00)3(11) \oplus 3(11) = 0(00)。

于是他想到了两个关于异或的问题,这两个问题基于一个给定的非负整数序列A1,A2,…,AnA_1, A_2, \dots, A_n,其中 nn 是该序列的长度。

第一个问题是,如果用 fi,jf_{i,j} 表示 Ai⊕Ai+1⊕⋯⊕AjA_i \oplus A_{i+1} \oplus \dots \oplus A_j,则任意的 1≤i≤j≤n1\le i\le j\le n 的 fi,jf_{i,j} 相加是多少。

第二个问题是,如果用 gi,jg_{i,j} 表示 Ai+Ai+1+⋯+AjA_i + A_{i+1} + \dots + A_j,则任意的 1≤i≤j≤n1\le i\le j\le n 的 gi,jg_{i,j} 异或在一起是多少。

比如说,对于序列 1,2{1,2},所有的 ff 是 {1,2,1⊕21, 2, 1 \oplus 2},加起来是 66;所有的 gg 是 {1,2,1+21, 2, 1 + 2},异或起来是 00。

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

输入格式

第一行一个正整数 nn,表示序列的长度。

第二行 nn 个非负整数 A1,A2,…,AnA_1, A_2, \dots, A_n,表示这个序列。

输出格式

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

2
1 2
6 0

数据范围

对于 100%100\% 的数据满足 n≤105n\le 10^5,Ai≤106A_i\le 10^6。