问题 4825 --2.卡牌选取

4825: 2.卡牌选取

题目描述

  一共有 $n$ 张卡牌,每张卡牌上有一个正整数 $A_i$,每次可以从中选出 $k$ 张卡牌。一种选取方案的幸运值为这 $k$ 张卡牌上数的按位异或和。
求所有选取方案的幸运值之和,对 $998244353$ 取模。

输入

输入的第一行有两个整数 $n$$k$
第二行有 $n$ 个整数,表示序列 $A$

输出

输出一行一个整数表示答案。

样例输入输出

输入#1 复制
3 2
1 2 3
输出#1 复制
6
输入#2 复制
10 5
123 456 789 987 654 321 101 202 303 404
输出#2 复制
130776

提示

【样例解释 1】
令 $\oplus $  表示异或运算,则幸运值之和为 $(1\oplus 2)+(1\oplus 3)+(2\oplus 3)=6$。
对于 $30\%$  的数据, $ n \leq 20$ ;
另有 $30\%$  的数据, $ n \leq 100, A_i \leq 1024 $ ;
对于 $80\%$  的数据, $ n \leq 2000 $ ;
对于 $100\%$  的数据, $ n \leq 10^5, 0\leq A_i \le 2^{31}, 1\leq k \leq n$。

序号 标题 作者 发表时间 费用 订购数 操作