1988C.md (1350B)
1 Source: https://codeforces.com/problemset/problem/1988/C 2 3 C. Increasing Sequence with Fixed OR 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given a positive integer $n$. Find the longest sequence of positive integers $a=[a_1,a_2,\ldots,a_k]$ that satisfies the following conditions, and print the sequence: 22 23 * $a_i\le n$ for all $1\le i\le k$. 24 * $a$ is strictly increasing. That is, $a_i \gt a_{i-1}$ for all $2\le i\le k$. 25 * $a_i\,|\,a_{i-1}=n$ for all $2\le i\le k$, where $|$ denotes the [bitwise OR operation](https://en.wikipedia.org/wiki/Bitwise_operation#OR). 26 27 Input 28 29 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). Description of the test cases follows. 30 31 The only line of each test case contains one integer $n$ ($1\le n\le 10^{18}$). 32 33 It's guaranteed that the sum of lengths of the longest valid sequences does not exceed $5\cdot 10^5$. 34 35 Output 36 37 For each testcase, print two lines. In the first line, print the length of your constructed sequence, $k$. In the second line, print $k$ positive integers, denoting the sequence. If there are multiple longest sequences, you can print any of them. 38 39 Example 40 41 Input 42 43 ``` 44 4 45 46 1 47 48 3 49 50 14 51 52 23 53 ``` 54 55 Output 56 57 ``` 58 1 59 1 60 3 61 1 2 3 62 4 63 4 10 12 14 64 5 65 7 18 21 22 23 66 ```