#MX100. Xor
Xor
题目描述
初始时给定一个长度为 的正整数序列 ,序列下标为 ,现有一个二维数组 ,执行以下函数
void init(){
for(int i=0;i<n;i++) b[0][i]=a[i];
for(int i=1;i<n;i++)
for(int j=0;j<n-i;j++) b[i][j]=b[i-1][j]^b[i-1][j+1];
}
现给出 次询问,每次询问给定非负整数 ,保证有 ,试给出 的权值大小。
提示:组合数
输入格式
第一行包含 个正整数 。
第二行给定长度为 的正整数序列 。
之后 行,每行给出 个参数 ,表示一次询问。
输出格式
输出 行,每行输出 个整数,表示最终答案。
样例 1 输入
4 4
9 5 9 2
1 2
0 0
0 2
3 0
样例 1 输出
11
9
9
7
样例解释
序列的形态为
9 5 9 2
12 12 11
0 7
7
样例 2 输入
见下发文件,数据保证每组询问的 为所有可能的询问中等概率生成的。
样例 2 输出
见下发文件。
评测数据规模
对于 的数据,。
对于 的数据,数据保证每组询问的 为所有可能的询问中等概率生成的。
对于所有测评数据,。