T422522 k耦合

题目描述

若两个数$x,y$，他们在二进制形式下有$k$位是不同的，我们称这两个数字是$k$耦合的。

例如二进制$1001$和$0110$是满足$4$耦合的，他们有$4$位不同

现在给出一个非负整数序列$a_1,a_2,.....,a_n$，你需要求存在多少对$(i,j),i<j$使得$a_i,a_j$是满足$k$耦合的。

输入格式

第一行输入$n,k$，表示序列长度和耦合要求

第二行输入$n$个数，表示序列$a$

输出格式

输出一个数字表示答案

样例 #1

样例输入 #1

text

4 1
0 3 2 1

样例输出 #1

text

4

样例 #2

样例输入 #2

text

6 0
200 100 100 100 200 200

样例输出 #2

text

6

提示

数据范围：

$(2 ≤ n ≤ 10^5, 0 ≤ k ≤ 14)$

$(0 ≤ a_i ≤ 10^4)$

---

题解

首先最先想到的是枚举$i$,$j$判断$a_i$,$a_j$是否为k耦合。时间复杂度尾或者$O(n^2)$。得到的结果是超超时。考虑优化，我们发现题目所给的值域只有$10^4$，也就是说会出现重复的数字，我们对0到10000依次枚举计算是不会超时的，所以我们需要统计重复的数字来避免重复计算，减少时间。

首先我们可以创建一大小为略大于$10^4$数组，下表表示这个数，对应的值表示出现的次数。

int mp[10004]={0};

然后我们依次枚举计算是否符合条件即可。

k耦合的判断方法为$a_i$^$a_j$，因为考虑异或二进制位上相同则为0，考虑两数字异或后有二进制上有几个1即可。计算一个数的二进制上有几个一有2种办法：

法一：mod2法

int a;
int cnt=0;
cin>>a;
while (a!=0)
{
    if (a%2==1)
    {
        cnt++;
    }
    a/=2;
}
cout<<cnt<<endl;

法二：位运算法

int b;
int cnt=0;
cin>>b;
while (b!=0)
{
    cnt+=b&1;
    b>>=1;
}
cout<<cnt<<endl;

下面是完整代码：

#include<bits/stdc++.h>
using namespace std;
bool check(int a,int k)
{
    int b=a;
    int cnt=0;
    while (b!=0)
    {
        cnt+=b&1;
        b>>=1;
    }
    return cnt==k;
}
int main()
{
    int n,k;
    long long sum=0;
    cin>>n>>k;
    int temp;
    int mp[10004]={0};
    for (int i=1;i<=n;i++)
    {
        cin>>temp;
        mp[temp]++;
    }
    if (k==0)
    {
        for (int i=0;i<=10000;i++)
        {
            if (mp[i]>0)
            {
                sum+=mp[i]*(mp[i]-1);
            }
        }
        sum/=2;
    }
    else
    {
        for (int i=0;i<10000;i++)
        {
            if (mp[i]>0)
            {
                for (int j=i+1;j<=10000;j++)
                {
                    if (mp[j]>0)
                    {
                        if (check(i^j,k))
                        {
                            sum+=mp[i]*mp[j];
                        }
                    }
                }
            }
        }
    }
    cout<<sum<<endl;
    return 0;
}