type
status
date
slug
summary
tags
category
icon
password
题目描述
若两个数，他们在二进制形式下有位是不同的，我们称这两个数字是耦合的。
例如二进制和是满足耦合的，他们有位不同
现在给出一个非负整数序列，你需要求存在多少对使得是满足耦合的。
输入格式
第一行输入，表示序列长度和耦合要求
第二行输入个数，表示序列
输出格式
输出一个数字表示答案
样例 #1
样例输入 #1
样例输出 #1
样例 #2
样例输入 #2
样例输出 #2
提示
数据范围：
题解
首先最先想到的是枚举判断是否为k耦合。时间复杂度尾或者。得到的结果是超超时。考虑优化，我们发现题目所给的值域只有，也就是说会出现重复的数字，我们对0到10000依次枚举计算是不会超时的，所以我们需要统计重复的数字来避免重复计算，减少时间。
首先我们可以创建一大小为略大于数组，下表表示这个数，对应的值表示出现的次数。
然后我们依次枚举计算是否符合条件即可。
k耦合的判断方法为^，因为考虑异或二进制位上相同则为0，考虑两数字异或后有二进制上有几个1即可。计算一个数的二进制上有几个一有2种办法：
法一：mod2法
法二：位运算法
下面是完整代码：
- Author:Serendipity
- URL:https://serendipity565.netlify.app//article/T422522%20k%E8%80%A6%E5%90%88
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!