#311. 计算几何

计算几何

题目描述

九条可怜是一个喜欢计算几何的女孩子,她画了一个特别的平面坐标系,其中 xx 轴正半轴与 yy 轴正半轴夹角为 6060 度。

从中,她取出所有横纵坐标不全为偶数,且满足 $-2a + 1 \le x \le 2a - 1,~-2b + 1 \le y \le 2b - 1,~-2c + 1 \le x + y \le 2c - 1$ 的整点。

可怜想将q 其中一些点染色,但相邻的点不能同时染色。具体地,对于点 (x, y)(x,~y),它和 $(x,~y + 1),~(x,~y - 1),~(x + 1,~y),~(x - 1,~y),~(x + 1,~y - 1),~(x - 1,~y + 1)$ 六个点相邻,可结合样例解释理解。

可怜想知道在这个规则下最多能将多少点染色,以及染最多点的染色方案数。由于后者值可能很大,对于染色方案数,你只需要输出对 998244353998244353 取模后的结果。注意不需要将最多染色点数取模。

输入格式

从文件 geometry.in 中读入数据。

第一行一个整数 TT 代表数据组数。

接下来 TT 行,每行三个整数 a, b, ca,~b,~c 代表一组数据。

输出格式

输出到文件 geometry.out 中。

输出共 TT 行,每行两个整数,代表最多能染的点数**(不取模)**和方案数对 998244353998244353 取模的结果。

6
2 1 2
1 1 137
3 94 95
3 1998 1996
998244 353999 999999
50 120 150
7 4
4 1
1124 31585548
23951 33873190
1289433675488 748596399
23600 480090154

如下图所示,点 JJ 的坐标为 (2, 1)(2,~1),点 FF 的坐标为 (1, 0)(-1,~0),点 HH 的坐标为 (2, 0)(2,~0)。在这三个点中,只有点 HH 是横纵坐标全为偶数的点。图中与点 AA 距离为 11 的点有 BCDEFGBCDEFG 六个点。

在样例的第一组数据中,满足条件的整点有 RNGBIJPFCKMLEDSTRNGBIJPFCKMLEDST

最多能染 77 个点,方案共 44 种,具体为:PNLBDJTPNLBDJTRMFBDJTRMFBDJTRMGECJTRMGECJTRMGEISKRMGEISK

在样例的第二组数据中,满足条件的整点有 GBIFCLEDGBIFCLED.

最多能染 44 个点,方案共 11 种,具体为:LGIDLGID

数据范围与提示

对于所有测试点:保证 1T10, 1a,b,c1061 \le T \le 10,~1 \le a,b,c \le 10^6

每个测试点的具体限制见下表:

测试点编号 aa \le b,cb,c \le 特殊限制
11 33 a=b=ca = b = c
22 44
33
44 33 100100
5, 65,~6 10001000
7, 87,~8 50005000
9, 109,~10 100100 a=b=ca = b = c
111411 \sim 14
1515 10510^5 a=b=ca = b = c
1616
17, 1817,~18 10610^6 a×b×c106a \times b \times c \le 10^6
1919 a=b=ca = b = c
2020