問題一覧 > 通常問題

No.1189 Sum is XOR

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 94
作問者 : EbishuEbishu / テスター : RhoRho
7 ProblemId : 4874 / 出題時の順位表
問題文最終更新日: 2020-08-24 20:00:48

問題文

 長さ $N$ の正整数列 $A$ が与えられます。

以下の条件を満たす長さ $K$ の数列 $B$ が何通りあるか求めてください。ただし、条件を満たす数列が存在しない場合は $0$ 通りとします。

  • $1\leq B_1< B_2<\cdots< B_K\leq N$
  • $A_{B_1}+A_{B_2}+\cdots+A_{B_K}=A_{B_1}\ xor\ A_{B_2}\ xor\ \cdots\ xor\ A_{B_K}$
ここで、正整数 $a, b$ に対して $a\ xor\ b$ は $a$ と $b$ のビットごとの排他的論理和を表します。

 答えは非常に大きくなる場合があるので、 $998244353$ で割った余りを出力してください。

入力

$N\ K$
$A_1\ A_2\ \cdots\ A_N$
  • 入力は全て整数
  • $2\leq N\leq 2\times10^5$
  • $2\leq K\leq N$
  • $1\leq A_i\leq 2^{10}-1\ (1\leq i\leq N)$

出力

答えを $998244353$ で割った余りを出力して、最後に改行してください。

サンプル

サンプル1
入力
3 2
1 2 5
出力
2

  • $A_1+A_2=A_1\ xor\ A_2=3$ であり、$1\leq 1< 2 \leq 3$ なので、数列 $\{1,2\}$ は条件を満たします。
  • $A_2+A_3=A_2\ xor\ A_3=7$ であり、$1\leq 2< 3 \leq 3$ なので、数列 $\{2,3\}$ は条件を満たします。
他の数列はいずれも条件を満たさないので、 $2$ を出力します。

サンプル2
入力
2 2
1 2
出力
1

  • $A_1+A_2=A_1\ xor\ A_2=3$ であり、$1\leq 1< 2 \leq 2$ なので、数列 $\{1,2\}$ は条件を満たします。
他の数列はいずれも条件を満たさないので、 $1$ を出力します。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。