304852: CF922B. Magic Forest

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Magic Forest

题意翻译

### 题目大意 给定一个正整数$n$ ,求满足如下条件的三元组$(a,b,c)$ 的个数: - $1 \le a \le b \le c \le n$ - $a \space xor \space b \space xor \space c=0$ - 存在一个边长分别为$a,b,c$ 的三角形。 ### 输入格式 一行一个正整数$n(1 \le n \le 2500)$ ### 输出格式 输出满足题意的三元组个数。 感谢U3144 浮尘ii 提供的翻译

题目描述

Imp is in a magic forest, where xorangles grow (wut?) ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF922B/eea79d64d5bc09a90f356e81b9be908191dfc1cd.png)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 $ ; - ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF922B/e65927e7d4505d57752956035449f810615b89fe.png), where ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF922B/7f1c9cbc3c887d7630734a437576c704fecc514a.png) 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.

输入输出格式

输入格式


The only line contains a single integer $ n $ $ (1<=n<=2500) $ .

输出格式


Print the number of xorangles of order $ n $ .

输入输出样例

输入样例 #1

6

输出样例 #1

1

输入样例 #2

10

输出样例 #2

2

说明

The only xorangle in the first sample is $ (3,5,6) $ .

Input

题意翻译

### 题目大意 给定一个正整数$n$ ,求满足如下条件的三元组$(a,b,c)$ 的个数: - $1 \le a \le b \le c \le n$ - $a \space xor \space b \space xor \space c=0$ - 存在一个边长分别为$a,b,c$ 的三角形。 ### 输入格式 一行一个正整数$n(1 \le n \le 2500)$ ### 输出格式 输出满足题意的三元组个数。 感谢U3144 浮尘ii 提供的翻译

加入题单

上一题 下一题 算法标签: