1848: 命运之夜
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：49
解决：14
题目描述
小A被圣杯选为第N次圣杯战争的master了，为了在这场残酷的战争中活下去并赢得圣杯，小A希望可以召唤出最强的英灵。为此，他拿出了自己的全部家当。但是，召唤出最强的英灵是有条件的，小A通过询问他在英国的魔术师朋友了解到，如果他想召唤出最强英灵，他需要准备两个圣遗物x,y。x，y的价值需要满足:x OR y和x AND y的二进制表示中值为 1 的位数之和大于等于k ，其中 OR 是按位 或 操作，而 AND 是按位 与 操作。现在，小A一共有n件圣遗物，第i个圣遗物的价值为ai，他想知道他有多少种方案可以召唤出最强英灵。
输入
第一行两个整数n，k，n表示小A拥有的圣遗物的数量，k表示召唤出最强英灵需要的条件（2<=n<=100000，0<=k<=60）。
第二行n个整数（a1，a2, a3......an）第i个数表示第i件圣遗物的价值（0<ai<=109）;
输出
一个整数，表示小A有多少种方案召唤出最强英灵。
样例输入 复制
4 3
1 2 3 1样例输出 复制
3提示
样例解释：
1.选择第一个和第三个，1 AND 3 ＝2，1 OR 3＝3，2的二进制位中有一个1，3的二进制位中有两个1，二者之和大于等于3。
2.选择第三个和第四个，1 AND 3 ＝2，1 OR 3＝3，2的二进制位中有一个1，3的二进制位中有两个1，二者之和大于等于3。
3.选择第二个和第三个，2 AND 3 ＝2，2 OR 3＝3，2的二进制位中有一个1，3的二进制位中有两个1，二者之和大于等于3。
除此之外，没有别的组合了。