1614C.md (3049B)
1 Source: https://codeforces.com/problemset/problem/1614/C 2 3 C. Divan and bitwise operations 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Once Divan analyzed a sequence $a_1, a_2, \ldots, a_n$ consisting of $n$ non-negative integers as follows. He considered each non-empty subsequence of the sequence $a$, computed the [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) of its elements and added up all the XORs, obtaining the coziness of the sequence $a$. 22 23 A sequence $c$ is a subsequence of a sequence $d$ if $c$ can be obtained from $d$ by deletion of several (possibly, zero or all) elements. For example, $[1, \, 2, \, 3, \, 4]$, $[2, \, 4]$, and $[2]$ are subsequences of $[1, \, 2, \, 3, \, 4]$, but $[4, \, 3]$ and $[0]$ are not. 24 25 Divan was very proud of his analysis, but now he lost the sequence $a$, and also the coziness value! However, Divan remembers the value of [bitwise OR](https://en.wikipedia.org/wiki/Bitwise_operation#OR) on $m$ contiguous subsegments of the sequence $a$. It turns out that each element of the original sequence is contained in at least one of these $m$ segments. 26 27 Divan asks you to help find the coziness of the sequence $a$ using the information he remembers. If several coziness values are possible, print any. 28 29 As the result can be very large, print the value modulo $10^9 + 7$. 30 31 Input 32 33 The first line contains one integer number $t$ ($1 \le t \le 10^3$) — the number of test cases. 34 35 The first line of each test case contains two integer numbers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$) — the length of the sequence and the number of contiguous segments whose bitwise OR values Divan remembers, respectively. 36 37 The following $m$ lines describe the segments, one per line. 38 39 Each segment is described with three integers $l$, $r$, and $x$ ($1 \le l \le r \le n$, $0 \le x \le 2^{30} - 1$) — the first and last elements of the segment and the bitwise OR of $a_l, a_{l + 1}, \ldots, a_r$, respectively. 40 41 It is guaranteed that each element of the sequence is contained in at least one of the segments. It is guaranteed that there exists a sequence that satisfies all constraints. 42 43 It is guaranteed that the sum of $n$ and the sum of $m$ over all test cases do not exceed $2 \cdot 10^5$. 44 45 Output 46 47 For each test case print the coziness any suitable sequence $a$ modulo $10^9 + 7$. 48 49 Example 50 51 Input 52 53 ``` 54 3 55 2 1 56 1 2 2 57 3 2 58 1 3 5 59 2 3 5 60 5 4 61 1 2 7 62 3 3 7 63 4 4 0 64 4 5 2 65 ``` 66 67 Output 68 69 ``` 70 4 71 20 72 112 73 ``` 74 75 Note 76 77 In first example, one of the sequences that fits the constraints is $[0, 2]$. Consider all its non-empty subsequences: 78 79 * $[0]$: the bitwise XOR of this subsequence is $0$; 80 * $[2]$: the bitwise XOR of this subsequence is $2$; 81 * $[0, 2]$: the bitwise XOR of this subsequence is $2$. 82 83 The sum of all results is $4$, so it is the answer. 84 85 In second example, one of the sequences that fits the constraints is $[0, \, 5, \, 5]$. 86 87 In third example, one of the sequences that fits the constraints is $[5, \, 6, \, 7, \, 0, \, 2]$.