UOJ Logo Universal Online Judge

UOJ

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

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

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

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

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

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

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

爱是一个$p×q$的$01$矩阵$A$,而惩罚是一个$q×s$的$01$矩阵$B$。

命运的果实由爱与惩罚组成,即满足 $C[i][j]=(\sum\limits_{k=1}^qA[i][k]×B[k][j]) \pmod 2$。

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

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

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

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

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

输入格式

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

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

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

输出格式

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

样例一

input

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

output

6
18

限制与约定

对于全部数据,都有$1\le p,q,s,m\le 1000$,$k\in\{0,1\}$ 。

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

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

特性$B$表示$p=q=s$。

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

子任务编号数据范围数据特性该任务分值
1$n\le 3,m=0$ 4
2$n\le 4,m=0$ 6
3$n\le 5,m=0$ 5
4$n\le 300,m=0$ 15
5$n\le 300,m\le 1000$ 11
6$n\le 700,m=0$AB7
7$n\le 1000,m=0,p=s$C6
8$n\le 1000,m=0$ 16
9$p,q,m\le 1000,s\le 100,k=0$ 12
10$n,m\le 1000$A10
11$n,m\le 1000$ 8

时间限制:$\texttt{1s}$

空间限制:$\texttt{512MB}$

下载

样例数据下载