題干：

Imp is in a magic forest, where xorangles grow (wut?)

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?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.

Examples

Input

6

Output

1

Input

10

Output

2

Note

The only xorangle in the first sample is?(3,?5,?6）.

題目大意：

問你有多少個非嚴格遞增的三個數(shù)a,b,c,滿足a^b^c=0.

解題報告：

? ? 這題因為異或的性質(zhì)，a^a=0，0^c=c。所以在三元組中，枚舉前兩小的值，那么第三個值其實就已知了。也就是這三個值一定是a? ,? b? ,? a^b。然后把題目那些條件帶進去做判斷就可以了

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; int n; int main() {cin>>n;ll ans = 0;for(int i = 1; i<=n; i++) {for(int j = i; j<=n; j++) {if((i^j)<=n &&(i^j)>=j&&(i+j) > (i^j)) {//printf("%d %d\n",i,j);ans++;}}}printf("%lld\n",ans);return 0 ;}

?

總結(jié)

以上是生活随笔為你收集整理的【CodeForces - 922B 】Magic Forest （数学，异或，暴力，水题，三元组问题）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。