問題一覧 > 通常問題

No.2990 Interval XOR

レベル : / AI推定難易度 : 2925 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 18
作問者 : akakimidori / テスター : noshi91
お気に入りにしたユーザー ProblemId : 10111 / 自分の提出
問題文最終更新日: 2024-12-13 22:31:19
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2024 (順位表) の他の問題:

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.

  1. $L_i \leq A_i \leq R_i (1 \leq i \leq M)$
  2. $A_1 \oplus A_2 \oplus \cdots \oplus A_M = x$
Here, $\oplus$ denotes the bitwise $\mathrm{XOR}$ operation.
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.
For example, $3 \oplus 5 = 6$ (in binary: $011 \oplus 101 = 110$).
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もしくは右上の雲マークをクリックしてアカウントを作成してください。