922B.md (1390B)
1 Source: https://codeforces.com/problemset/problem/922/B 2 3 B. Magic Forest 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 Imp is in a magic forest, where xorangles grow (wut?) 22 23  24 25 A xorangle of order *n* is such a non-degenerate triangle, that lengths of its sides are integers not exceeding *n*, and the xor-sum of the lengths is equal to zero. Imp has to count the number of distinct xorangles of order *n* to get out of the forest. 26 27 Formally, for a given integer *n* you have to find the number of such triples (*a*, *b*, *c*), that: 28 29 * 1 ≤ *a* ≤ *b* ≤ *c* ≤ *n*; 30 * , where  denotes the [bitwise xor](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) of integers *x* and *y*. 31 * (*a*, *b*, *c*) form a non-degenerate (with strictly positive area) triangle. 32 33 Input 34 35 The only line contains a single integer *n* (1 ≤ *n* ≤ 2500). 36 37 Output 38 39 Print the number of xorangles of order *n*. 40 41 Examples 42 43 Input 44 45 ``` 46 6 47 ``` 48 49 Output 50 51 ``` 52 1 53 ``` 54 55 Input 56 57 ``` 58 10 59 ``` 60 61 Output 62 63 ``` 64 2 65 ``` 66 67 Note 68 69 The only xorangle in the first sample is (3, 5, 6).