26465번 - Sharp 2-SAT 다국어

This problem is about the special case of the Satisfiability Problem (SAT). Let's introduce the definition of SAT first.

A SAT instance is a boolean logic formula consisting of several boolean variables combined by AND, OR, and NOT operators and parentheses. An assignment is a mapping from variable to boolean value. An assignment is satisfying a formula if and only if the formula is evaluated to be true with the given assignment. A literal is either a variable or its negation. A clause is a list of literals concatenated with OR. A formula is in Conjunctive Normal Form (CNF) if it consists of clauses concatenated with AND. In the following, we only consider CNF formulae as SAT inputs because every formula can be converted to the equivalent CNF formula. 2-SAT is a special case of SAT where the length of clauses are limited to 2. For example, $(x ∨ y) ∧ (¬x ∨ z)$ is a 2-SAT instance consisting of $3$ variables and $2$ clauses. $x =$ false, $y =$ true, $z =$ true is one of the satisfying assignments for this formula.

You are given a 2-SAT instance in CNF with $N$ variables and $M$ clauses. The $i$-th variable is denoted by $x_i$ and this $i$ is called index. In all clauses, the difference between the indices of the two variables is less than or equal to $2$.

Let $C_k$ be the number of satisfying assignments where exactly $k$ variables are true. Your task is to write a program that calculates $C_k$ for all $k$s $0$ from to $N$.

Since the answer may be huge, print the answer modulo $998\,244\,353$.

The input consists of a single test case with the following format.

$N$ $M$

$A_1$ $B_1$

$\vdots$

$A_M$ $B_M$

The first line consists of two integers, the number of variables $N$ ($1 ≤ N ≤ 100\,000$) and the number of clauses $M$ ($1 ≤ M ≤ 100\,000$).

The following $M$ lines represent the clauses in the 2-SAT instance. Each line corresponds to one of the clauses. These lines contain $2$ integers $A_i$ and $B_i$ representing the literals in the clause. They satisfy $1 ≤ |A_i | , |B_i | ≤ N$ and $||A_i | − |B_i || ≤ 2$ and each of them has the following meaning: If it is a positive integer $a$, the literal is $x_a$ (without negation). If it is a negative integer $b$, the literal is $¬x_{-b}$ (with negation).

Output $N+1$ lines. The $i$-th line contains a single integer $C_{i-1}$ modulo $998\,244\,353$.