B. Magic Forest

Codeforces

IDCF922B

Time1000ms

Memory256MB

Difficulty—

brute force

English · Original

Chinese · Translation

Formal · Original

Imp is in a magic forest, where xorangles grow (wut?) <center>![image](https://espresso.codeforces.com/41a89e297f110aa906c319b9c9c581669469c1f7.png)</center>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. Formally, for a given integer _n_ you have to find the number of such triples (_a_, _b_, _c_), that: * 1 ≤ _a_ ≤ _b_ ≤ _c_ ≤ _n_; * , where denotes the [bitwise xor](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) of integers _x_ and _y_. * (_a_, _b_, _c_) form a non-degenerate (with strictly positive area) triangle. ## Input The only line contains a single integer _n_ (1 ≤ _n_ ≤ 2500). ## Output Print the number of xorangles of order _n_. [samples] ## Note The only xorangle in the first sample is (3, 5, 6).

Imp 在一个魔法森林中，那里生长着 xorangles（什么？）一个阶为 #cf_span[n] 的 xorangle 是指一个非退化三角形，其三边长度为不超过 #cf_span[n] 的整数，且三边长度的交错和等于零。Imp 需要计算阶为 #cf_span[n] 的不同 xorangle 的数量，才能走出这片森林。形式化地，给定整数 #cf_span[n]，你需要找出满足以下条件的三元组 #cf_span[(a, b, c)] 的数量：输入仅包含一行，一个整数 #cf_span[n] #cf_span[(1 ≤ n ≤ 2500)]。请输出阶为 #cf_span[n] 的 xorangle 的数量。第一个样例中唯一的 xorangle 是 #cf_span[(3, 5, 6)]。 ## Input 输入仅包含一行，一个整数 #cf_span[n] #cf_span[(1 ≤ n ≤ 2500)]。 ## Output 请输出阶为 #cf_span[n] 的 xorangle 的数量。 [samples] ## Note 第一个样例中唯一的 xorangle 是 #cf_span[(3, 5, 6)]。

**Definitions** Let $ n \in \mathbb{Z} $ with $ 1 \leq n \leq 2500 $. A *xorangle of order $ n $* is a triple $ (a, b, c) \in \mathbb{Z}^3 $ such that: - $ 1 \leq a \leq b \leq c \leq n $, - $ a \oplus b \oplus c = 0 $, - $ a + b > c $ (non-degenerate triangle condition). **Constraints** $ 1 \leq n \leq 2500 $ **Objective** Count the number of distinct triples $ (a, b, c) $ satisfying the above conditions.

Samples

Input #1

Output #1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "B. Magic Forest",
    "description": {
      "content": "Imp is in a magic forest, where xorangles grow (wut?) <center>![image](https://espresso.codeforces.com/41a89e297f110aa906c319b9c9c581669469c1f7.png)</center>A xorangle of order _n_ is such a non-dege",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF922B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Imp is in a magic forest, where xorangles grow (wut?)\n\n<center>![image](https://espresso.codeforces.com/41a89e297f110aa906c319b9c9c581669469c1f7.png)</center>A xorangle of order _n_ is such a non-dege...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Imp 在一个魔法森林中，那里生长着 xorangles（什么？）\n\n一个阶为 #cf_span[n] 的 xorangle 是指一个非退化三角形，其三边长度为不超过 #cf_span[n] 的整数，且三边长度的交错和等于零。Imp 需要计算阶为 #cf_span[n] 的不同 xorangle 的数量，才能走出这片森林。\n\n形式化地，给定整数 #cf_span[n]，你需要找出满足以下条件的三元...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ with $ 1 \\leq n \\leq 2500 $.  \nA *xorangle of order $ n $* is a triple $ (a, b, c) \\in \\mathbb{Z}^3 $ such that:  \n- $ 1 \\leq a \\leq b \\leq c \\leq n $,  \n- $...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments