#2415. 计算几何

    ID: 2415 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>PROV赛事:contest922来源:qoj.ac数据:公开样例计算几何动态规划枚举

计算几何

计算几何

题目描述

ZJOI 2022 第二试 计算几何(geometry) 计算几何(geometry) 【题目描述】 九条可怜是一个喜欢计算几何的女孩子,她画了一个特别的平面坐标系,其中x 轴正半轴与y 轴正半轴夹角为60 度。 从中,她取出所有横纵坐标不全为偶数,且满足−2a + 1 ≤x ≤2a −1, −2b + 1 ≤y ≤2b −1, −2c + 1 ≤x + y ≤2c −1 的整点。 可怜想将其中一些点染色,但相邻的点不能同时染色。具体地,对于点(x, y),它和(x, y + 1), (x, y −1), (x + 1, y), (x −1, y), (x + 1, y −1), (x −1, y + 1) 六个点相邻,可结合样例解释理解。 可怜想知道在这个规则下最多能将多少点染色,以及染最多点的染色方案数。由于后者值可能 很大,对于染色方案数,你只需要输出对998 244 353 取模后的结果。注意不需要将最多染色点数取 模。 【输入格式】 从文件geometry.in 中读入数据。 第一行一个整数T 代表数据组数。 接下来T 行,每行三个整数a, b, c 代表一组数据。 【输出格式】 输出到文件geometry.out 中。 输出共T 行,每行两个整数,代表最多能染的点数(不取模)和方案数对998 244 353 取模的结 果。 【样例输入】 见下发文件中的geometry ex1.in。 【样例输出】 见下发文件中的geometry ex1.ans。 第6 页 共9 页

ZJOI 2022 第二试 计算几何(geometry) 【数据范围与提示】 对于所有测试点:1 ≤T ≤10, 1 ≤a, b, c ≤106 。 每个测试点的具体限制见下表: 测试点编号 a ≤ b, c ≤ 特殊限制 1 3 3 a = b = c 2 4 4 a = b = c 3 4 4 无 4 3 100 无 5, 6 3 1 000 无 7, 8 3 5 000 无 9, 10 100 100 a = b = c 11 ∼14 100 100 无 15 105 105 a = b = c 16 105 105 无 17, 18 106 106 a · b · c ≤106 19 106 106 a = b = c 20 106 106 无 【样例解释】 如下图所示,点J 的坐标为(2, 1) ,点F 的坐标为(−1, 0) ,点H 的坐标为(2, 0) 。在这三个 点中,只有点H 是横纵坐标全为偶数的点。图中与点A 距离为1 的点有BCDEFG 六个点。 在样例的第一组数据中,满足条件的整点有RNGBIJPFCKMLEDST。 最多能染7 个点,方案共4 种,具体为:PNLBDJT,RMFBDJT,RMGECJT,RMGEISK。 在样例的第二组数据中,满足条件的整点有GBIFCLED 。 最多能染4 个点,方案共1 种,具体为:LGID 。 第7 页 共9 页

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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