| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 2048 MB | 14 | 8 | 8 | 57.143% |
Busy Beaver lived on an unpainted sidewalk consisting of $N$ individual tiles numbered 1,2,ドル\dots,N$ from left to right. The tiles all start with the factory-standard color 0ドル,ドル but Busy Beaver is looking to change that! Over several days of painting, Busy Beaver aims to repaint the entire sidewalk.
Specifically, Busy Beaver wrote down a list of $Q$ plans, the $i$-th of which states that on day $d_i$ (0ドル \le d_i \le 2^K-1$), Busy Beaver will repaint all tiles in the range $[x_i, y_i]$ with color $c_i,ドル overwriting their previous colors. Busy Beaver has at most one painting plan scheduled for each day, and he is interested in the sum of the final colors of all tiles after all the repaintings.
Unbeknownst to Busy Beaver, he is, in fact, the first Beaver to live in a Quantum Computer! This unfortunately means that the universe does not operate as he thinks it does. During the night, while no one is watching, the qubits undergo a random transformation: an integer $z$ between 0ドル$ and 2ドル^K - 1$ is selected, and every plan originally scheduled for day $i$ is instead moved to day $i \oplus z,ドル where $\oplus$ denotes \href{https://en.wikipedia.org/wiki/Bitwise_operation#XOR}{bitwise XOR}.
For a given $z,ドル the plans are then executed in increasing order of their (shifted) day, and each repaint operation overwrites the colors of the tiles between $x_i$ and $y_i$. Let $F(z)$ be the sum of the final colors of all tiles after applying the plans with shift $z$.
Compute ${\large \sum_{z=0}^{2^K - 1}} F(z)$. Since the answer may be enormous, output it modulo 10ドル^9+7$.
Each test contains multiple test cases. The first line contains the number of test cases $T$ (1ドル\leq T\leq 150$). The description of the test cases follows.
The first line of each test case contains three integers $N,ドル $K,ドル and $Q$ (1ドル\leq N\leq 2\cdot10^5,ドル 0ドル\leq K\leq60,ドル 1ドル\leq Q\leq \min(2^K,2\cdot 10^5)$).
The $i$-th of the next $Q$ lines contains four integers $d_i,ドル $x_i,ドル $y_i,ドル and $c_i$ (0ドル\leq d_i<2^K,ドル 1ドル\leq x_i\leq y_i\leq N,ドル 0ドル\leq c_i\leq10^9$).
It is guaranteed that the sum of $N$ across all test cases is at most 4ドル\cdot10^5,ドル the sum of $Q$ across all test cases is at most 4ドル\cdot10^5,ドル and all $d_i$'s within a test case are distinct.
For each test case, output one integer on its own line: the sum of the answers to Busy Beaver's original question over all 2ドル^K$ possible shifts, modulo 10ドル^9+7$.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | The sum of $N,ドル 2ドル^K,ドル and $Q$ over all test cases are each less than or equal to 5ドル \cdot 10^3$. Note that this refers to each of the individual sums, not the cumulative sum of all of them. Also, $c_i \le 5 \cdot 10^3$ for all $i$. |
| 2 | 20 | For all test cases, $N=1, Q \le 2$. |
| 3 | 20 | For all test cases, $N=1$. |
| 4 | 20 | For all test cases, $K\leq 18$. |
| 5 | 30 | No further constraints. |
3 6 4 6 6 3 5 4 12 2 2 3 4 1 4 2 5 3 3 4 14 1 1 3 13 1 6 4 6 4 4 4 1 2 0 3 2 6 4 2 2 2 2 5 3 5 0 4 4 6 8 2 4 2 11 1 3 2 9 3 4 4 10 3 3 2 2 3 4 3 3 1 4 5
332 184 220
3 5 4 4 9 1 2 2 12 1 3 1 10 4 5 3 14 1 5 4 6 4 4 5 2 4 3 14 5 6 2 10 3 6 3 1 4 6 5 6 4 5 11 2 4 5 13 1 2 4 14 4 6 5 10 1 6 3 15 2 6 0
224 272 276