P16117 [USTCPC 2026] Evil Counting Problem

“Waa—! How can there be such a weird array!” Kruskal-chan stared at the blackboard full of $+1$ and $-1$, and felt completely overwhelmed. “Senior, senior!” the junior tugged at her sleeve. “If I give you an interval, and the numbers inside can be rearranged freely, then how many rearrangements make the sum of products of all contiguous subsegments equal to $k$ exactly?” Facing those sparkling eyes, Kruskal-chan could only bite the bullet and accept the challenge. Sigh, today’s club activity seems not so peaceful again……

You are given an array $a$ of length $n$, where each element is either $\pm 1$. You are also given a constant $k$ and $q$ queries. Each query specifies $l, r$. You need to compute: assuming you may arbitrarily permute the elements whose indices are in $[l, r]$, how many permutations make the sum of products of all non-empty subsegments of the new array (still of length $n$), i.e. $\sum_{i\le j}\prod_{t\in[i,j]}a_t$, equal to $k$. Output the result modulo $998244353$. Note: even if two different permutations produce exactly the same resulting array, they are still considered different permutations.

**This problem contains multiple test cases.** The first line contains an integer $T$ ($1\le T\le 10^5$), the number of test cases. For each test case, the first line contains three integers: the array length $n$ ($1\le n\le 10^5$), the constant $k$ ($\lvert k\rvert\le\frac{n(n+1)}{2}$), and the number of queries $q$ ($1\le q\le 10^5$). The next line contains $n$ integers. The $i$-th integer is $a_i$, satisfying $\lvert a_i\rvert=1$. Then follow $q$ lines. Each line contains two integers. The two integers on the $i$-th line are $l_i, r_i$ for the $i$-th query ($1\le l_i\le r_i\le n$). It is guaranteed that $\sum n, \sum q\le 10^5$.

Output $\sum q$ lines, each containing one integer, the answer to the corresponding query.

For the first query of the first sample, the first four elements must be rearranged into $(1,-1,1,-1)$ or $(-1,1,-1,1)$. There are $8$ permutations in total that satisfy the requirement. Translated by ChatGPT 5