UOJ Logo Universal Online Judge

UOJ

#453. 【集训队作业2018】围绕着我们的圆环

附件下载 统计
“悲伤的事和艰辛的事,我不认为它们徒劳无益。  
如果那就是命运的话,就必然有其意义。  
我会全部接受它们并变得坚强。  
所以——请为我驻足。”  
                           ——《回转企鹅罐》

如果命运从一开始就被写好了,那么生存的意义是什么呢?

我想为了你活下去,我想你为了我活下去。

只要有一个人需要,那么活着就是有意义的。

lihua与Rosemary一起分享了命运的果实,一起分担了爱与惩罚。

命运是一个既定的 p×s01矩阵 C,它是确定的。

爱是一个p×q01矩阵A,而惩罚是一个q×s01矩阵B

命运的果实由爱与惩罚组成,即满足 C[i][j]=(k=1qA[i][k]×B[k][j])(mod2)

命运即使已经既定,但是爱与惩罚的可能性很多,lihua与Rosemary不禁想要计算。

而他们也不会顺从着搭上命运的列车,到达命运所至之地,他们也会换乘自己的命运。

因此存在m次命运换乘,lihua与Rosemary在命运换乘点以爱之名念出了咒语,换乘了命运。

命运换乘会将矩阵C的某一行进行修改,每次修改后lihua与Rosemary希望重新计算爱与惩罚的可能性。

由于可能性可能十分多样,他们只希望了解模1000000007后的答案。

输入格式

第一行五个整数,分别表示p,q,s,m,k

接下来读入矩阵C,共p行每行s个数。

再接下来m行表示修改,每一行一开始一个数 j表示修改的是矩阵第jxor(kans)行,其中ans表示修改前的答案。然后接下来s个数表示将这行修改成什么。

输出格式

在所有修改前及每次修改后输出一行一个整数表示答案。

样例一

input

2 2 2 1 0
0 1
1 0
1 1 0

output

6
18

限制与约定

对于全部数据,都有1p,q,s,m1000k{0,1}

n表示p,q,s的最大值。

特性A表示数据随机,初始矩阵、每次修改哪一行以及修改成什么样都是随机生成。如果没有多余限制,则p,q,s均在(n5,n]中随机生成(如subtask 10 )。若限制p=q=s=o,那么o(n100,n]中随机生成(如subtask 6)。

特性B表示p=q=s

特性C表示初始读入的矩阵C是单位矩阵。

子任务编号数据范围数据特性该任务分值
1n3,m=0 4
2n4,m=0 6
3n5,m=0 5
4n300,m=0 15
5n300,m1000 11
6n700,m=0AB7
7n1000,m=0,p=sC6
8n1000,m=0 16
9p,q,m1000,s100,k=0 12
10n,m1000A10
11n,m1000 8

时间限制:1s

空间限制:512MB

下载

样例数据下载