No.1189 Sum is XOR
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 128
作問者 : Ebishu / テスター : Rho
タグ : / 解いたユーザー数 128
作問者 : Ebishu / テスター : Rho
問題文最終更新日: 2020-12-02 16:59:59
問題文
長さ $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}$
答えは非常に大きくなる場合があるので、 $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
1 2
出力
1
- $A_1+A_2=A_1\ xor\ A_2=3$ であり、$1\leq 1< 2 \leq 2$ なので、数列 $(1,2)$ は条件を満たします。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。