{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003edd \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background-color: #f5f5f5;\n border: 1px solid #ccc;\n border-radius: 4px;\n}\u003c/style\u003e","sections":[{"title":"Description","value":{"format":"HTML","content":"\u003cdiv\u003e背景\u003c/div\u003e\r\n\u003cdiv\u003e\u003c/div\u003e\r\n\u003cdiv\u003e小Q学习位运算时发现了异或的秘密。\u003c/div\u003e\r\n\u003cdiv\u003e\u003c/div\u003e\r\n\u003cdiv\u003e描述\u003c/div\u003e\r\n\u003cdiv\u003e\u003c/div\u003e\r\n\u003cdiv\u003e小Q是一个热爱学习的人,他经常去维基百科(http://en.wikipedia.org/wiki/Main_Page)学习计算机科学。\u003c/div\u003e\r\n\u003cdiv\u003e\u003c/div\u003e\r\n\u003cdiv\u003e就在刚才,小Q认真地学习了一系列位运算符(http://en.wikipedia.org/wiki/Bitwise_operation),其中按位异或的运算符 xor 对他影响很大。按位异或的运算符是双目运算符。按位异或具有交换律,即i xor j \u003d j xor i。\u003c/div\u003e\r\n\u003cdiv\u003e\u003c/div\u003e\r\n\u003cdiv\u003e他发现,按位异或可以理解成被运算的数字的二进制位对应位如果相同,则结果的该位置为0,否则为1,例如1(01) xor 2(10) \u003d 3(11)。\u003c/div\u003e\r\n\u003cdiv\u003e\u003c/div\u003e\r\n\u003cdiv\u003e他还发现,按位异或可以理解成数字的每个二进制位进行了不进位的加法,例如3(11) xor 3(11) \u003d 0(00)。\u003c/div\u003e\r\n\u003cdiv\u003e\u003c/div\u003e\r\n\u003cdiv\u003e于是他想到了两个关于异或的问题,这两个问题基于一个给定的非负整数序列A1, A2, ..., An,其中n是该序列的长度。\u003c/div\u003e\r\n\u003cdiv\u003e\u003c/div\u003e\r\n\u003cdiv\u003e第一个问题是,如果用f(i, j)表示Ai xor Ai+1 xor ... xor Aj,则任意的1 \u0026lt;\u003d i \u0026lt;\u003d j \u0026lt;\u003d n的f(i, j)相加是多少。\u003c/div\u003e\r\n\u003cdiv\u003e\u003c/div\u003e\r\n\u003cdiv\u003e第二个问题是,如果用g(i, j)表示Ai + Ai+1 + ... + Aj,则任意的1 \u0026lt;\u003d i \u0026lt;\u003d j \u0026lt;\u003d n的g(i, j)异或在一起是多少。\u003c/div\u003e\r\n\u003cdiv\u003e\u003c/div\u003e\r\n\u003cdiv\u003e比如说,对于序列{1, 2},所有的f是{1, 2, 1 xor 2},加起来是6;所有的g是{1, 2, 1 + 2},异或起来是0。\u003c/div\u003e\r\n\u003cdiv\u003e\u003c/div\u003e\r\n\u003cdiv\u003e他觉得这两个问题都非常的有趣,所以他找到了你,希望你能快速解决这两个问题,其中第一个问题的答案可能很大,你只需要输出它对998244353(一个质数)取模的值即可。\u003c/div\u003e\r\n\u003cdiv\u003e\u003c/div\u003e\r\n\u003cp class\u003d\"MsoNormal\" align\u003d\"left\"\u003e\u003c/p\u003e\r\n\u003cp\u003e\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv\u003e第一行一个正整数n,表示序列的长度。\u003c/div\u003e\r\n\u003cdiv\u003e\r\n\u003cdiv\u003e\u003c/div\u003e\r\n\u003cdiv\u003e第二行n个非负整数A1, A2, ..., An,表示这个序列。\u003c/div\u003e\r\n\u003cdiv\u003e\u003c/div\u003e\r\n\u003c/div\u003e\r\n\u003cp\u003e\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv\u003e两个整数,表示两个问题的答案,空格隔开,其中第一个问题的答案要对998244353(一个质数)取模。\u003c/div\u003e\r\n\u003cdiv\u003e\r\n\u003cdiv\u003e\u003c/div\u003e\r\n\u003c/div\u003e\r\n\u003cp\u003e\u003c/p\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2 \r\n1 2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6 0\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cdiv\u003e100%的数据满足n \u0026lt;\u003d 10^5, Ai \u0026lt;\u003d 10^6。\u003c/div\u003e\u003cbr\u003e\r\n\u003cdiv\u003e\u003c/div\u003e\u003cbr\u003e\r\n\u003cp\u003e\u003c/p\u003e"}}]}