4320. bitset(位集)

【题目背景】

“生是死的开始” 

“死亡是现实的延续” 

“而重生，是一场梦的终结。” 

“笑容是假的”

 “真相就是痛苦” 

“融化的心摧毁了我”

———《新世纪福音战士》

【题目描述】

定义了大小为 $m$ 的 bitset 为长度为 $m$ 的 bool 数组

对于大小为 $m$ 的 bitset 定义如下四种运算:

    1.$c = a \text{ and } b$：在这里。如果 $a_i = 1$ 且 $b_i = 1$，则 $c_i = 1$；否则 $c_i = 0$

    2.$c = a \text{ or } b$：在这里。如果 $a_i = 1$ 或 $b_i = 1$，则 $c_i = 1$；否则 $c_i = 0$

    3.$c = a \text{ xor } b$：在这里。如果 $a_i$ 和 $b_i$ 中恰好有一个为 $1$，则 $c_i = 1$；否则 $c_i = 0$

    4.$c = \text{ not } a$：在这里。如果 $a_i = 0$，则 $c_i = 1$；否则 $c_i = 0$

给定一个大小为 $n$ 的 bitset 数组 $s_1, s_2, \dots, s_n$，编写程序来回答 $k$ 个查询，每次查询给定$l,r$，你需要使用以下公式计算$t$:

$t=(s_l \space \text{and}\space s_{l+1} \space \text{and } \cdots \text{ and } s_r) \text{ xor } (\text{not }(s_l \text{ or } s_{l+1} \text{ or } \cdots \text{ or } s_r))$

求 $t$ 中 1 的个数

【输入格式】

第一行包含两个整数 $n$ 和 $m$($1 \leq n, m \leq 10^7$)。接下来 $n$ 行描述了 $n$ 个bitset，每行由 $m$ 个 0 或 1 组成，表示一个 bitset。

接下来的一行包括一个整数 $k$，表示查询的数量($1 \leq k \leq 2 \times 10^6$)。

接下来的一行包括三个整数 $x,y,z$($1 \leq x, y, z \leq 10^9$)。

查询是通过以 $x,y,z$ 为参数的伪随机算法生成的，具体来说，考虑生成长度为 $k$ 的序列 $a,b$:

    $a_1 = 1$

    $b_1 = n$

    对于$i > 1$，$a_i = (a_{i-1} \cdot x + q_{i-1} \cdot y + z) \bmod n + 1$。

    对于$i > 1$，$b_i = (b_{i-1} \cdot y + q_{i-1} \cdot z + x) \bmod n + 1$

其中，第 $i$ 个询问的 $l$ 是 $\min\{a_i,b_i\}$，$r$ 是 $\max\{a_i,b_i\}$，公式里的 $q_{i-1}$ 表示 $i - 1$ 个询问的答案。

【输出格式】

输出一个整数表示所有查询答案的总和。

【样例输入】

4 10
1010110101
0101111001
1101101101
1011010000
4
10 5 4

【样例输出】

9

【数据规模与约定】

对于所有数据，有：

    $1 \le n,m \le 10^7$

    $nm \le 10^7$

    $1 \le k \le 2 \times 10^6$

    $1 \le x,y,z \le 10^9$

大洋里

子任务：

【来源】

qoj P7717