No.2990 Interval XOR
タグ : / 解いたユーザー数 18
作問者 :
akakimidori
/ テスター :
noshi91
Problem Statement
You are given an integer $N$ and a sequence of $M$ integer pairs $(L_1, R_1), (L_2, R_2), \cdots, (L_M, R_M)$. Here, $0 \leq L_i \leq R_i \leq 2^N - 1$ holds for every integer $i (1 \leq i \leq M)$.
For each integer $x$ satisfying $0 \leq x \leq 2^N - 1$, find the number, modulo $998244353$, of integer sequences $A$ of length $M$ that satisfy all of the following conditions.
- $L_i \leq A_i \leq R_i (1 \leq i \leq M)$
- $A_1 \oplus A_2 \oplus \cdots \oplus A_M = x$
What is the bitwise $\mathrm{XOR}$ operation?
The bitwise $\mathrm{XOR}$ of non-negative integers $A, B$, denoted $A \oplus B$, is defined as follows.
- When $A \oplus B$ is written in binary, the digit in the $2^k (k \geq 0)$ place is $1$ if exactly one of the digits in the $2^k$ place of $A, B$ written in binary is $1$, and $0$ otherwise.
In general, the bitwise $\mathrm{XOR}$ of $k$ non-negative integers $p_1, p_2, p_3, \dots, p_k$ is defined as $(\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k)$, and it can be proved that this does not depend on the order of $p_1, p_2, p_3, \dots p_k$.
Input
$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)$
- All inputs are integers.
Output
Print $2^N$ lines.
On the $i+1 (0 \leq i \leq 2^N - 1)$-th line, print the answer for $x=i$.
Print a newline at the end.
Sample
Sample 1
Input
2 2 1 2 0 2
Output
2 1 1 2
For $x = 0$, there are two sequences $A$ satisfying the conditions: $(1, 1), (2, 2)$.
For $x = 1$, there is one sequence $A$ satisfying the conditions: $(1, 0)$.
For $x = 2$, there is one sequence $A$ satisfying the conditions: $(2, 0)$.
For $x = 3$, there are two sequences $A$ satisfying the conditions: $(1, 2), (2, 1)$.
Sample 2
Input
3 2 1 3 3 7
Output
1 1 1 0 3 3 3 3
For $x=3$, no sequence satisfies the conditions, so print $0$.
Sample 3
Input
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
Output
420295125 420295121 420298041 420298037 362514049 362514053 362511133 362511137 296364049 296364053 296361133 296361137 354145125 354145121 354148041 354148037
Note that you should print the remainder when divided by $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。