bzoj#P4017. 小Q的无敌异或

小Q的无敌异或

题目描述

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

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

就在刚才,小Q认真地学习了一系列位运算符,其中按位异或的 运算符 \oplus 对他影响很大。按位异或的运算符是双目运算符。按位异或具有交换律,即 ij=jii \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} 表示 AiAi+1AjA_i \oplus A_{i+1} \oplus \dots \oplus A_j,则任意的 1ijn1\le i\le j\le nfi,jf_{i,j} 相加是多少。

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

比如说,对于序列 1,2{1,2},所有的 ff 是 {1,2,121, 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\% 的数据满足 n105n\le 10^5,Ai106A_i\le 10^6