30361번 - Empty Quartz 다국어

$N$ crystals are aligned in a row. However, some of them may be phantoms.

Jun counted the number of real crystals from $l$-th to $r$-th (closed interval) for every $l$, $r$ ($1 \le l \le r \le N$) pair and recorded their evenness.

His $\frac{N(N+1)}{2}$ records show that there were $k$ intervals that contained an odd number of real crystals. How many possible crystal alignments are there? Answer the remainder divided by $998244353$.

Note that if there is $i$ such that the $i$-th crystal from the left is real on one side and phantom on the other, the two alignments are considered different.

You are given $T$ of the above problems. Answer each of them.

$T$

$N_1$ $K_1$

$\vdots$

$N_T$ $K_T$

Output $T$ lines. On the line $i$, answer the problem when $N = N_i$, $K = K_i$. Add a new line at the end of each line.

• All inputs consist of integers.
• $1 \le T \le 10^5$
• $1 \le N_i \le 10^5$
• $0 \le K_i \le \frac{N_i(N_i+1)}{2}$

If we denote a real crystal as $1$ and an phantom as $0$, the following three alignments satisfy the condition at Sample Input 1.

• $0, 1, 0$
• $1, 0, 1$
• $1, 1, 1$