codeforces-scrape

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

1329B.md (1369B)


      1 Source: https://codeforces.com/problemset/problem/1329/B
      2 
      3 B. Dreamoon Likes Sequences
      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 Dreamoon likes sequences very much. So he created a problem about the sequence that you can't find in OEIS:
     22 
     23 You are given two integers $d, m$, find the number of arrays $a$, satisfying the following constraints:
     24 
     25 * The length of $a$ is $n$, $n \ge 1$
     26 * $1 \le a_1 \lt a_2 \lt \dots \lt a_n \le d$
     27 * Define an array $b$ of length $n$ as follows: $b_1 = a_1$, $\forall i \gt 1, b_i = b_{i - 1} \oplus a_i$, where $\oplus$ is the bitwise exclusive-or (xor). After constructing an array $b$, the constraint $b_1 \lt b_2 \lt \dots \lt b_{n - 1} \lt b_n$ should hold.
     28 
     29 Since the number of possible arrays may be too large, you need to find the answer modulo $m$.
     30 
     31 Input
     32 
     33 The first line contains an integer $t$ ($1 \leq t \leq 100$) denoting the number of test cases in the input.
     34 
     35 Each of the next $t$ lines contains two integers $d, m$ ($1 \leq d, m \leq 10^9$).
     36 
     37 Note that $m$ is not necessary the prime!
     38 
     39 Output
     40 
     41 For each test case, print the number of arrays $a$, satisfying all given constrains, modulo $m$.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 10
     49 1 1000000000
     50 2 999999999
     51 3 99999998
     52 4 9999997
     53 5 999996
     54 6 99995
     55 7 9994
     56 8 993
     57 9 92
     58 10 1
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 1
     65 3
     66 5
     67 11
     68 17
     69 23
     70 29
     71 59
     72 89
     73 0
     74 ```