Digital Circuit | 프로그래밍의 벗 PivotOJ

문제

There is a circuit, which consists of $N + M$ gates numbered from $0$ to $N + M - 1$ . Gates $0$ to $N - 1$ are threshold gates, whereas gates $N$ to $N + M - 1$ are source gates.

Each gate, except for gate $0$ , is an input to exactly one threshold gate. Specifically, for each $i$ such that $1 \le i \le N + M - 1$ , gate $i$ is an input to gate $P [i]$ , where $0 \le P[i] \le N-1$ . Importantly, we also have $P[i] \lt i$ . Moreover, we assume $P [0] = - 1$ . Each threshold gate has one or more inputs. Source gates do not have any inputs.

Each gate has a state which is either $0$ or $1$ . The initial states of the source gates are given by an array $A$ of $M$ integers. That is, for each $j$ such that $0 \le j \le M - 1$ , the initial state of the source gate $N + j$ is $A [j]$ .

The state of each threshold gate depends on the states of its inputs and is determined as follows. First, each threshold gate is assigned a threshold parameter. The parameter assigned to a threshold gate with $c$ inputs must be an integer between $1$ and $c$ (inclusive). Then, the state of a threshold gate with parameter $p$ is $1$ , if at least $p$ of its inputs have state $1$ , and $0$ otherwise.

For example, suppose there are $N = 3$ threshold gates and $M = 4$ source gates. The inputs to gate $0$ are gates $1$ and $6$ , the inputs to gate $1$ are gates $2$ , $4$ , and $5$ , and the only input to gate $2$ is gate $3$ .

This example is illustrated in the following picture.

Suppose that source gates $3$ and $5$ have state $1$ , while source gates $4$ and $6$ have state $0$ . Assume we assign parameters $1$ , $2$ and $2$ to threshold gates $2$ , $1$ and $0$ respectively. In this case, gate $2$ has state $1$ , gate $1$ has state $1$ and gate $0$ has state $0$ . This assignment of parameter values and the states is illustrated in the following picture. Gates whose state is $1$ are marked in black.

The states of the source gates will undergo $Q$ updates. Each update is described by two integers $L$ and $R$ ( $N \le L \le R \le N + M - 1$ ) and toggles the states of all source gates numbered between $L$ and $R$ , inclusive. That is, for each $i$ such that $L \le i \le R$ , source gate $i$ changes its state to $1$ , if its state is $0$ , or to $0$ , if its state is $1$ . The new state of each toggled gate remains unchanged until it is possibly toggled by one of the later updates.

Your goal is to count, after each update, how many different assignments of parameters to threshold gates result in gate $0$ having state $1$ . Two assignments are considered different if there exists at least one threshold gate that has a different value of its parameter in both assignments. As the number of ways can be large, you should compute it modulo $1\,000\,002\,022$ .

Note that in the example above, there are $6$ different assignments of parameters to threshold gates, since gates $0$ , $1$ and $2$ have $2$ , $3$ and $1$ inputs respectively. In $2$ out of these $6$ assignments, gate $0$ has state $1$ .