題干：

Vasya has the sequence consisting of?n?integers. Vasya consider the pair of integers?x?and?y?k-interesting, if their binary representation differs from each other exactly in?k?bits. For example, if?k?=?2, the pair of integers?x?=?5?and?y?=?3?is?k-interesting, because their binary representation?x=101?and?y=011?differs exactly in two bits.

Vasya wants to know how many pairs of indexes (i,?j) are in his sequence so that?i?<?j?and the pair of integers?ai?and?aj?is?k-interesting. Your task is to help Vasya and determine this number.

Input

The first line contains two integers?n?and?k?(2?≤?n?≤?105,?0?≤?k?≤?14) — the number of integers in Vasya's sequence and the number of bits in which integers in?k-interesting?pair should differ.

The second line contains the sequence?a1,?a2,?...,?an?(0?≤?ai?≤?104), which Vasya has.

Output

Print the number of pairs (i,?j) so that?i?<?j?and the pair of integers?ai?and?aj?is?k-interesting.

Examples

Input

4 1 0 3 2 1

Output

4

Input

6 0 200 100 100 100 200 200

Output

6

Note

In the first test there are 4?k-interesting?pairs:

• (1,?3),
• (1,?4),
• (2,?3),
• (2,?4).

In the second test?k?=?0. Consequently, integers in any?k-interesting?pair should be equal to themselves. Thus, for the second test there are 6?k-interesting?pairs:

• (1,?5),
• (1,?6),
• (2,?3),
• (2,?4),
• (3,?4),
• (5,?6).

題目大意：

給你N個數的一個序列a，如果有兩個數二進制中有K個位置不同，那么對應就算作一對可行解，問一共有多少對可行解。

(2?≤?n?≤?1e5,?0?≤?k?≤?14,?0?≤?ai?≤?1e4)

解題報告：

? 介紹這個題的兩種寫法。首先很顯然看x和y有多少個位子不同，直接看x^y對應的二進制中1的個數即可。

所以第一種想法啊十分好想，預處理1~20000所有數字的1的個數，然后暴力枚舉1e4以內的每個數字i和j，如果i^1的1的個數等于k，則直接統計i，j兩個數的出現次數。我這里偷懶了沒預處理，直接用內置函數了。這種方法復雜度O(1e8)

第二種方法就是讀入完k之后，先暴力枚舉所有1的個數等于k的數，打表可以發現對任意一個k，1e4以內不會超過3000個數。問題等價于求x^y=z，x和y符合的二元組個數，已知x<=1e4，z最多3000個，所以直接枚舉x和z來反求y。復雜度O(3e8)左右。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 1<<15; int n,k; int dp[MAX]; vector<int> vv; int cnt[MAX],mx; ll ans; int main() { // cout << (1<<14) << endl;cin >> n >> k;for(int x,i = 1; i<=n; i++) {scanf("%d",&x); dp[x]++; mx = max(mx,x);}if(k == 0) {for(int i = 0; i<=mx; i++) ans += 1LL*dp[i]*(dp[i]-1)/2;cout << ans << endl; return 0;}for(int i = 0; i<=mx; i++) {for(int j = i+1; j<=mx; j++) {if(__builtin_popcount(i^j) == k) {ans += 1LL*dp[i] * dp[j];}}} cout << ans << endl;return 0 ; }

?

總結

以上是生活随笔為你收集整理的【Codeforces - 769D】k-Interesting Pairs Of Integers（暴力，统计，思维，数学，异或）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。