레이팅 미적용A game is given on a sequence of length \(N\), initially filled with zeros. During the
game, we color positions in the sequence using a series of operations, and we can
stop coloring after any operation.
The \(X\)-th coloring operation is described by the following procedure:
• We select a position containing 0.
• We decide whether to:
– Paint the selected position with - 1.
– Paint the selected position with color \(X\) and continue painting adjacent
positions to the left with color \(X\). We stop painting when we encounter
a position with a value different than 0 (which we do not paint) or when
we go out of the sequence bounds.
Two games are considered equivalent if, in their final sequences, we can rename the colors greater than 0,
i.e., if there is a bijective mapping such that:
• Colors after mapping remain greater than 0.
• Each color receives exactly one new label.
• After mapping, both sequences are identical.
An example of equivalent games is:
• [1, 1, −1, 2, −1, 3, 0]
• [3, 3, −1, 1, −1, 2, 0]
because there is a mapping of colors (color 1 to color 3, color 2 to color 1, color 3 to color 2) such that all
the above conditions are satisfied.
There are \(Q\) updates given, where for each update, we swap all 0s with - 1s and all - 1s with 0s in the
interval [L, R] in the sequence.
After each update, print the number \(K\), the number of different games that can be played with an arbitrary
number of operations such that no two games are equivalent. Since \(K\) is very large, print the result
modulo \(10^{9} + 7\).
In the first line, there are 2 natural numbers \(N\), \(Q\) (\(1 \le N \le 10^{18}\), \(1 \le Q \le 10^{5}\)), representing the number
of fields in the sequence and the number of updates.
In the following \(Q\) lines, there are two natural numbers, \(L\) and \(R\) (\(1 \le L\), \(R \le N\)), indicating the positions
that describe the update from the problem statement.
In the \(i\)-th of the following \(Q\) lines, print the remainder of the division of the number \(K\) by \(10^{9} + 7\) after
each update.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 20점 | N, \(Q \le 1000\) |
2 | 55점 | \(N \le 10^{6}\) |
3 | 45점 | No additional constraints. |
1 2
1 1
1 11
33 2
2 2
1 39
357 2
13 39
6 42130653412
804077942Clarification of the first example: After the first update, the sequence is equal to [−1]. We cannot
perform any operations on it, so the maximum number of games we can play is 1. After the second
update, the sequence is equal to [0]. From the sequence [0], using the operations described in the problem
statement, we can create the sequences [0], [1], and [−1]. We observe that no pair of these sequences is
equivalent, so the maximum number of games we can play is 3.