A6586 | 「ZJOI2022」计算几何
时间限制1s
内存限制1024MB
通过 / 提交0/0
题目描述
九条可怜是一个喜欢计算几何的女孩子，她画了一个特别的平面坐标系，其中 $x$ 轴正半轴与 $y$ 轴正半轴夹角为 $60$ 度。
从中，她取出所有横纵坐标不全为偶数，且满足 $-2 a + 1 \le x \le 2 a - 1$，$-2 b + 1 \le y \le 2 b - 1$，$-2 c + 1 \le x + y \le 2 c - 1$ 的整点。
可怜想将其中一些点染色，但相邻的点不能同时染色。具体地，对于点 $(x, y)$，它和 $(x, y + 1), (x, y - 1), (x + 1, y), (x - 1, y), (x + 1, y - 1), (x - 1, y + 1)$ 六个点相邻，可结合样例解释理解。
可怜想知道在这个规则下最多能将多少点染色，以及染最多点的染色方案数。由于后者值可能很大，对于染色方案数，你只需要输出对 $998244353$ 取模后的结果。**注意不需要将最多染色点数取模。**
从中，她取出所有横纵坐标不全为偶数，且满足 $-2 a + 1 \le x \le 2 a - 1$，$-2 b + 1 \le y \le 2 b - 1$，$-2 c + 1 \le x + y \le 2 c - 1$ 的整点。
可怜想将其中一些点染色，但相邻的点不能同时染色。具体地，对于点 $(x, y)$，它和 $(x, y + 1), (x, y - 1), (x + 1, y), (x - 1, y), (x + 1, y - 1), (x - 1, y + 1)$ 六个点相邻，可结合样例解释理解。
可怜想知道在这个规则下最多能将多少点染色，以及染最多点的染色方案数。由于后者值可能很大，对于染色方案数，你只需要输出对 $998244353$ 取模后的结果。**注意不需要将最多染色点数取模。**
输入格式
第一行一个整数 $T$ 代表数据组数。
接下来 $T$ 行，每行三个整数 $a, b, c$ 代表一组数据。
接下来 $T$ 行，每行三个整数 $a, b, c$ 代表一组数据。
输出格式
输出共 $T$ 行，每行两个整数，代表最多能染的点数（**不取模**）和方案数对 $998244353$ 取模的结果。
输入输出样例
输入 #1
6 2 1 2 1 1 137 3 94 95 3 1998 1996 998244 353999 999999 50 120 150
输出 #1
7 4 4 1 1124 31585548 23951 33873190 1289433675488 748596399 23600 480090154
对于所有测试点：$1 \le T \le 10$，$1 \le a, b, c \le {10}^6$。
每个测试点的具体限制见下表：
| 测试点编号 | $a \le$ | $b, c \le$ | 特殊限制 |
|:-:|:-:|:-:|:-:|
| $1$ | $3$ | $3$ | $a = b = c$ |
| $2$ | $4$ | $4$ | $a = b = c$ |
| $3$ | $4$ | $4$ | 无 |
| $4$ | $3$ | $100$ | 无 |
| $5 \sim 6$ | $3$ | $1000$ | 无 |
| $7 \sim 8$ | $3$ | $5000$ | 无 |
| $9 \sim 10$ | $100$ | $100$ | $a = b = c$ |
| $11 \sim 14$ | $100$ | $100$ | 无 |
| $15$ | ${10}^5$ | ${10}^5$ | $a = b = c$ |
| $16$ | ${10}^5$ | ${10}^5$ | 无 |
| $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$ | 无 |
每个测试点的具体限制见下表：
| 测试点编号 | $a \le$ | $b, c \le$ | 特殊限制 |
|:-:|:-:|:-:|:-:|
| $1$ | $3$ | $3$ | $a = b = c$ |
| $2$ | $4$ | $4$ | $a = b = c$ |
| $3$ | $4$ | $4$ | 无 |
| $4$ | $3$ | $100$ | 无 |
| $5 \sim 6$ | $3$ | $1000$ | 无 |
| $7 \sim 8$ | $3$ | $5000$ | 无 |
| $9 \sim 10$ | $100$ | $100$ | $a = b = c$ |
| $11 \sim 14$ | $100$ | $100$ | 无 |
| $15$ | ${10}^5$ | ${10}^5$ | $a = b = c$ |
| $16$ | ${10}^5$ | ${10}^5$ | 无 |
| $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$ | 无 |
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？