問題一覧 > 通常問題

No.1189 Sum is XOR

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 130
作問者 : EbishuEbishu / テスター : RhoRho
6 ProblemId : 4874 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-12-02 16:59:59

問題文

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

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

  • 1B1<B2<<BKN
  • AB1+AB2++ABK=AB1 xor AB2 xor  xor ABK
ここで、正整数 a,b に対して a xor bab のビットごとの排他的論理和を表します。

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

入力

N K
A1 A2  AN
  • 入力は全て整数
  • 2N2×105
  • 2KN
  • 1Ai2101 (1iN)

出力

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

サンプル

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

  • A1+A2=A1 xor A2=3 であり、11<23 なので、数列 (1,2) は条件を満たします。
  • A2+A3=A2 xor A3=7 であり、12<33 なので、数列 (2,3) は条件を満たします。
他の数列はいずれも条件を満たさないので、 2 を出力します。

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

  • A1+A2=A1 xor A2=3 であり、11<22 なので、数列 (1,2) は条件を満たします。
他の数列はいずれも条件を満たさないので、 1 を出力します。

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