No.2990 Interval XOR
タグ : / 解いたユーザー数 7
作問者 :
akakimidori
/ テスター :
noshi91
問題文
整数 $N$ と長さ $M$ の整数組の列 $(L_1, R_1), (L_2, R_2), \cdots, (L_M, R_M)$ が与えられます。 ただし全ての整数 $i (1 \leq i \leq M)$ に対して $0 \leq L_i \leq R_i \leq 2^N - 1$ が満たされています。
$0 \leq x \leq 2^N - 1$ を満たす整数 $x$ それぞれに対し、以下の条件をすべて満たす長さ $M$ の整数列 $A$ の個数を $998244353$ で割ったあまりを求めてください。
- $L_i \leq A_i \leq R_i (1 \leq i \leq M)$
- $A_1 \oplus A_2 \oplus \cdots \oplus A_M = x$
ビット単位 $\mathrm{XOR}$ 演算とは
非負整数 $A, B$ のビット単位 $\mathrm{XOR}$ 、$A \oplus B$ は、以下のように定義されます。
- $A \oplus B$ を二進表記した際の $2^k (k \geq 0)$ の位の数は、$A, B$ を二進表記した際の $2^k$ の位の数のうち一方のみが $1$ であれば $1$、そうでなければ $0$ である。
一般に $k$ 個の非負整数 $p_1, p_2, p_3, \dots, p_k$ のビット単位 $\mathrm{XOR}$ は $(\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k)$ と定義され、これは $p_1, p_2, p_3, \dots p_k$ の順番によらないことが証明できます。
入力
$N\ M$ $L_1\ R_1$ $\vdots$ $L_M\ R_M$
- $0 \leq N \leq 20$
- $1 \leq M \leq 2 \times 10^5$
- $ 0 \leq L_i \leq R_i \leq 2^N - 1 (1 \leq i \leq M)$
- 入力は全て整数
出力
$2^N$ 行出力してください。
$i+1 (0 \leq i \leq 2^N - 1)$ 行目には $x=i$ である時の答えを出力してください。
最後に改行してください。
サンプル
サンプル1
入力
2 2 1 2 0 2
出力
2 1 1 2
$x = 0$ の時条件を満たす数列 $A$ は $(1, 1), (2, 2)$ の2つです。
$x = 1$ の時条件を満たす数列 $A$ は $(1, 0)$ の1つです。
$x = 2$ の時条件を満たす数列 $A$ は $(2, 0)$ の1つです。
$x = 3$ の時条件を満たす数列 $A$ は $(1, 2), (2, 1)$ の2つです。
サンプル2
入力
3 2 1 3 3 7
出力
1 1 1 0 3 3 3 3
$x=3$の時、条件を満たす数列は存在しないので $0$ を出力します。
サンプル3
入力
4 20 3 10 4 10 3 10 6 14 7 12 3 10 4 10 11 14 6 14 5 13 6 14 0 6 5 15 0 14 3 15 8 14 4 10 5 13 2 14 7 13
出力
420295125 420295121 420298041 420298037 362514049 362514053 362511133 362511137 296364049 296364053 296361133 296361137 354145125 354145121 354148041 354148037
$998244353$ で割ったあまりを出力することに注意してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。