問題一覧 > 通常問題

No.2061 XOR Sort

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 67
作問者 : taiga0629kyoprotaiga0629kyopro / テスター : nok0nok0 👑 ygussanyygussany
4 ProblemId : 8340 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-08-25 22:25:53

問題文

長さ $N$ の整数列 $A$ が与えられます。次の操作を順に行って長さ $N$ の数列 $B$ を作ります。($\mathrm{XOR}$ はビットごとの排他的論理和を表します)

  • 非負整数 $X$ を一つ選ぶ。
  • $i=1,2, \dots,N$ に対して $B_i=A_i \ \mathrm{XOR} \ X $ とする。
  • $B$ を昇順に並べ替える。
  • $i=1,2, \dots,N$ に対して $B_i$ を $B_i \ \mathrm{XOR} \ X $ に置き換える。

最終的な $B$ としてあり得るものは何通りありますか?答えを $998244353$ で割った余りを求めてください。 ただし、長さ $N$ の数列 $B$ と $B'$ が異なるとは、ある整数 $i$ ($1 \le i \le N$)が存在して、$B_i \neq B'_i$ が成立するということです。

入力

$N$
$A_1$ $A_2$ $\dots$ $A_N$

  • $1 \le N \le 2×10^5$
  • $0 \le A_i <2^{30}$
  • 入力は全て整数
  • 出力

    最終的な $B$ としてあり得るものの個数を $998244353$ で割った余りを出力してください。

    サンプル

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

    最終的な $B$ としてあり得るものは $(0,0,1),(1,0,0)$ の $2$ つです。

    サンプル2
    入力
    3
    1 0 2
    出力
    4

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