#P2015125. 矩阵

矩阵

矩阵

题目描述

创造一个世界只需要定义一个初状态和状态转移规则。

宏观世界的物体运动规律始终跟物体当前的状态有关,也就是说只要知道物体足够多的状态信息,例如位置、速度等,我们就能知道物体之后任意时刻的状态。

现在小M创造了一个简化的世界。

这个世界中,时间是离散的,物理规律是线性的:世界的初始状态可以用一个m维向量∗∗b∗∗(0)**b^{**(0)}表示,状态的转移方式用m×m的矩阵A表示。

若已知这个世界当前的状态是b,那么下一时刻就等于b左乘状态转移矩阵A,即∗∗Ab**A^b**。

这个世界中,物体的状态也是离散的,也就是说可以用整数表示。再进一步,整数都可以用二进制编码拆分为有限位0和1。因此,这里的矩阵A和向量b的每个元素都是0或1,矩阵乘法中的加法运算视为异或运算(xor),乘法运算视为与运算(and)。

具体地,设矩阵A第i行第j列的元素为ai,ja_{i,j},向量b的第i个元素为bib_i。那么乘法∗∗Ab**A^b**所得的第k个元素为

(ak,1¥∗∗anda_{k,1}¥**and**b_1)∗∗xor∗∗()**xor**(a_{k,2}∗∗and**and**b_2¥)xor⋯xor(ak,m∗∗anda_{k,m}**and**b_m$)

矩阵和矩阵的乘法也有类似的表达。

小M发现,这样的矩阵运算也有乘法结合律,例如有A(∗∗Ab**A^b)=(∗∗AA**A^A)b=∗∗A∗∗2**A^**2b。

为了保证自己创造的世界维度不轻易下降,小M保证了矩阵A可逆,也就是说存在一个矩阵∗∗A∗∗−1**A^{**-1},使得对任意向量d,都有∗∗A∗∗−1**A_{**-1}Ad=d。

小M想了解自己创造的世界是否合理,他希望知道这个世界在不同时刻的状态。

具体地,小M有n组询问,每组询问会给出一个非负整数k,小M希望你帮他求出∗∗A∗∗k**A^**kb。

输入格式

输入第一行包含一个整数m,表示矩阵和向量的规模。

接下来m行,每行包含一个长度为m的01串,表示矩阵A。

接下来一行,包含一个长度为m的01串,表示初始向量∗∗b∗∗(0)**b^{**(0)}。(∗∗b∗∗(0**b^{**(0})是列向量,这里表示它的转置)

注意:01串两个相邻的数字之间均没有空格。

接下来一行,包含一个正整数n,表示询问的个数。

最后n行,每行包含一个非负整数k,表示询问∗∗A∗∗k∗∗b∗∗(0)**A^**k**b^{**(0)}。

注意:k可能为0,此时是求∗∗A∗∗0∗∗b∗∗(0)=∗∗b∗∗(0)**A^**0**b^{**(0)}=**b^{**(0)}。

输出格式

输出n行,每行包含一个01串,表示对应询问中∗∗A∗∗k∗∗b∗∗(0)**A^**k**b^{**(0)}的结果。

注意:01串两个相邻的数字之间不要输出空格。

数据范围

(原站未提供,导入后需人工补齐)

样例

3
110
011
111
101
10
0
2
3
14
1
1325
6
124124
151
12312
101
010
111
101
110
010
100
101
001
100

提示

评测用例规模与约定

本题使用10个评测用例来测试你的程序。

对于评测用例1,m= 10,n= 100,k≤ 10^3。

对于评测用例2,m= 10,n= 100,k≤ 10^4。

对于评测用例3,m= 30,n= 100,k≤ 10^5。

对于评测用例4,m= 180,n= 100,k≤ 10^5。

对于评测用例5,m= 10,n= 100,k≤ 10^9。

对于评测用例6,m= 30,n= 100,k≤ 10^9。

对于评测用例7,m= 180,n= 100,k≤ 10^9。

对于评测用例8,m= 600,n= 100,k≤ 10^9。

对于评测用例9,m= 800,n= 100,k≤ 10^9。

对于评测用例10,m= 1000,n= 100,k≤ 10^9。