位运算(bit)
Time Limit:2000ms Memory Limit:64MB
【题目描述】
lyk最近在研究位运算。它发现除了xor,or,and外还有很多运算。它新定义了一种运算符“#”。具体地,可以由4个参数来表示。令a[i][j]表示i#j。其中i,j与a的值均∈[0,1]。当然问题可以扩展为>1的情况,具体地,可以将两个数分解为p位,然后对于每一位执行上述的位运算,再将这个二进制串转化为十进制就可以了。例如当a[0][0]=0,a[1][1]=0,a[0][1]=1,a[1][0]=1时,3#4在p=3时等于7,2#3在p=4时等于1(实际上就是异或运算)。现在lyk想知道的是,已知一个长为n的数列b。它任意选取一个序列c,满足 c1<c2<...<ck,其中1≤c1且ck≤n,定义这个序列的价值为b{c1}#b{c2}#...#b{ck}的平方。这里我们假设k是正整数,因此满足条件的c的序列个数一定是2^n−1 。lyk想知道所有满足条件的序列的价值总和是多少。由于答案可能很大,你只需输出答案对1,000,000,007取模后的结果即可。
【输入格式】(bit.in)
第一行两个数n,p。
第二行4个数表示a[0][0],a[0][1],a[1][0],a[1][1]。
第三行n个数表示bi(0<=bi<2^p)。
【输出格式】(bit.out)
一个数表示答案。
【输入样例】
3 30
0 1 1 0
1 2 3
【输出样例】
28
【样例解释】
{1}的价值为1,{2}的价值为4,{3}的价值为9,{1,2}的价值为9,{1,3}的价值为4,{2,3}的价值为1,{1,2,3}的价值为0,因此7个子集的价值总和为28。
【数据范围】
总共10组数据。
对于第1,2组数据n<=5。
对于第3,4组数据n<=10000,p=1。
对于第5组数据a值均为0。
对于第6组数据a值均为1。
对于第7组数据a[0][0]=0,a[1][0]=0,a[1][1]=1,a[0][1]=1。
对于第8,9组数据n<=1000,p<=10。
对于所有数据n<=10000,1<=p<=30。
【题目分析】
骗分的话看一下第五组数据,记得取模