codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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]$.