P8333 [ZJOI2022] Computational Geometry

Jiutiao Kelian is a girl who likes computational geometry. She drew a special plane coordinate system, where the angle between the positive $x$-axis and the positive $y$-axis is $60$ degrees. From it, she takes all integer points whose $x$- and $y$-coordinates are not both even, and that satisfy $-2 a + 1 \le x \le 2 a - 1$, $-2 b + 1 \le y \le 2 b - 1$, and $-2 c + 1 \le x + y \le 2 c - 1$. Kelian wants to color some of these points, but adjacent points cannot be colored at the same time. Specifically, for a point $(x, y)$, it is adjacent to the six points $(x, y + 1)$, $(x, y - 1)$, $(x + 1, y)$, $(x - 1, y)$, $(x + 1, y - 1)$, and $(x - 1, y + 1)$. You may understand this together with the sample explanation. Kelian wants to know the maximum number of points that can be colored under this rule, and the number of coloring schemes that achieve this maximum. Since the latter may be very large, for the number of schemes you only need to output it modulo $998244353$. **Note that you do not need to take the maximum number of colored points modulo anything.**

The first line contains an integer $T$, representing the number of test cases. The next $T$ lines each contain three integers $a$, $b$, and $c$, representing one test case.

Output $T$ lines in total. Each line contains two integers: the maximum number of points that can be colored (**not taken modulo**) and the number of schemes modulo $998244353$.

**[Sample Explanation]** As shown in the figure below, point $J$ has coordinates $(2, 1)$, point $F$ has coordinates $(-1, 0)$, and point $H$ has coordinates $(2, 0)$. Among these three points, only point $H$ has both coordinates even. In the figure, the points at distance $1$ from point $A$ are the six points $\texttt{B C D E F G}$. In the first sample test case, the integer points satisfying the conditions are $\texttt{R N G B I J P F C K M L E D S T}$. The maximum number of points that can be colored is $7$, and there are $4$ schemes, namely: $\texttt{P N L B D J T}$, $\texttt{R M F B D J T}$, $\texttt{R M G E C J T}$, and $\texttt{R M G E I S K}$. In the second sample test case, the integer points satisfying the conditions are $\texttt{G B I F C L E D}$. The maximum number of points that can be colored is $4$, and there is $1$ scheme, namely: $\texttt{L G I D}$.  **[Constraints]** For all test points: $1 \le T \le 10$, $1 \le a, b, c \le {10}^6$. The specific limits for each test point are shown in the table below: | Test Point ID | $a \le$ | $b, c \le$ | Special Constraints | |:-:|:-:|:-:|:-:| | $1$ | $3$ | $3$ | $a = b = c$ | | $2$ | $4$ | $4$ | $a = b = c$ | | $3$ | $4$ | $4$ | None | | $4$ | $3$ | $100$ | None | | $5 \sim 6$ | $3$ | $1000$ | None | | $7 \sim 8$ | $3$ | $5000$ | None | | $9 \sim 10$ | $100$ | $100$ | $a = b = c$ | | $11 \sim 14$ | $100$ | $100$ | None | | $15$ | ${10}^5$ | ${10}^5$ | $a = b = c$ | | $16$ | ${10}^5$ | ${10}^5$ | None | | $17 \sim 18$ | ${10}^6$ | ${10}^6$ | $a \cdot b \cdot c \le {10}^6$ | | $19$ | ${10}^6$ | ${10}^6$ | $a = b = c$ | | $20$ | ${10}^6$ | ${10}^6$ | None | Translated by ChatGPT 5