33334번 - Bitsets 다국어

Let us consider the following operations on bitsets of size $m$:

• $c = a\, \mathrm{ and }\, b$. Here, $c_i=1$ if both $a_i$ and $b_i$ are equal to $1$. Otherwise, $c_i=0$.
• $c = a\, \mathrm{ or }\, b$. Here, $c_i=1$ if either $a_i$ or $b_i$ is equal to $1$. Otherwise, $c_i=0$.
• $c = a\, \mathrm{ xor }\, b$. Here, $c_i=1$ if exactly one of $a_i$ and $b_i$ is equal to $1$. Otherwise, $c_i=0$.
• $c = \mathrm{ not }\, a$. Here, $c_i=1$ if $a_i$ is equal to $0$. Otherwise, $c_i=0$.

You are given an array of bitsets $s_1, s_2, \ldots, s_n$. Write a program that can answer $k$ queries of the following form:

1. Take two integers $\ell$ and $r$.
2. Find bitset $t$ using the formula: $t = (s_\ell \,\mathrm{ and }\, s_{\ell+1} \,\mathrm{ and }\, \ldots \,\mathrm{ and }\, s_r) \,\mathrm{ xor }\, (\mathrm{ not }\, (s_\ell \,\mathrm{ or }\, s_{\ell+1} \,\mathrm{ or }\, \ldots \,\mathrm{ or }\, s_r))$.
3. Count the number of ones in bitset $t$: it is the answer.

The first line contains two integers $n$ and $m$ ($1 \leq n, m \leq 10^5$; $n \cdot m \leq 10^6$). The following $n$ lines describe the $n$ bitsets, where each line consists of $m$ characters $0$ and $1$ representing the bits of that bitset.

The next line of the input contains a single integer $k$ ($1 \leq k \leq 2 \cdot 10^7$), which denotes the number of queries. The following line contains three integers $x$, $y$, and $z$ ($1 \leq x, y, z \leq 10^9$).

The queries are generated using pseudo-random numbers, with input parameters $x$, $y$, and $z$, and a sequence $q_1, q_2, \ldots, q_{k - 1}$ of answers to the queries. Define two sequences $a$ and $b$ as follows:

• $a_1 = 1$.
• $b_1 = n$.
• For $i > 1$, $a_i = (a_{i-1} \cdot x + q_{i-1} \cdot y + z) \bmod n + 1$.
• For $i > 1$, $b_i = (b_{i-1} \cdot y + q_{i-1} \cdot z + x) \bmod n + 1$.

For each query $i$, the parameters $\ell$ and $r$ are defined as $\ell=\min(a_i, b_i)$ and $r=\max(a_i, b_i)$.

Output a single integer: the sum of the answers for all queries.

The queries are listed below: