P9773 [HUSTFC 2023] Sequence Pairing

You have a sequence of length $n$: $a_1,a_2,\dots,a_n$. Initially, every element in the sequence satisfies $a_i=0$. Then you are given $n$ pairs of indices. Each pair is an integer pair $(l,r)$, meaning that $a_l$ and $a_r$ are paired. After each pairing, you must perform exactly one of the following two operations (you cannot do both): - Increase $a_l$ by $1$, then decrease $a_r$ by $1$. - Increase $a_r$ by $1$, then decrease $a_l$ by $1$. You are also told that these pairings follow a special rule: among the $2n$ integers appearing in the $n$ pairs, each index of the sequence appears exactly $2$ times. You want to know, among all possible choices of operations, how many result in $\sum_{i=1}^n a_i^2 = k$. Since the answer may be very large, output it modulo $998\,244\,353$.

The first line contains an integer $n\ (1\le n\le 2\cdot 10^5)$, the length of the sequence. The next $n$ lines each contain two integers $l_i,r_i\ (1\le l\le r \le n)$, describing the $i$-th pairing. It is guaranteed that these $2n$ integers satisfy the requirement in the statement. The last line contains an integer $k\ (0\le k \le 10^9)$, with the meaning as described above.

Output one integer: the number of operation plans such that $\sum_{i=1}^n a_i^2=k$, modulo $998\,244\,353$.

Translated by ChatGPT 5