UOJ Logo Universal Online Judge

UOJ

#981. 【UR #31】决战中途岛

附件下载 统计

English Problem Statement

素练风霜起,苍鹰画作殊。㧐身思狡兔,侧目似愁胡。

绦镟光堪擿,轩楹势可呼。何当击凡鸟,毛血洒平芜。

你是美军的一名王牌飞行员,正驾驶俯冲式战斗机执行轰炸日军“飞龙号”航空母舰的命令。

作战区域是一个三维空域,空域中的一个位置用 (x,y,z) 表示,其中 x,y 表示你在海面上的投影坐标,z 表示高度。不幸的是,日军的“零式”战斗机正从你的身后包抄过来,你只能在 y|x| 的空域飞行

一开始你位于 (0,1,h) 处,每过一个时刻你的高度 h 都会下降 1。出于一些战术目的,在一个时刻内,你会依次执行以下两种战术动作:

  1. 桶翻:横向移动一格(由 (x,y,z) 移动到 (x,y,z0.5),满足 |xx|=1);
  2. 机动:横向或纵向移动一格(由 (x,y,z) 移动到 (x,y,z0.5),满足 |xx|+|yy|=1)。

请注意,这个过程中你也不能离开 y|x| 的空域。

"飞龙号"目前正位于 (a,b) 静止不动,你的目标是在你的高度恰好为 0 时,让你在海面上的投影坐标恰好为 (a,b),以达到轰炸“飞龙号”的目的。

战况紧急,请你立即编写一个程序,计算轰炸计划的方案数,由于这个数字很大,请输出答案对 998244353 取模后的值。

两个轰炸计划不同当且仅当存在一个点 (x,y,z),其中一个方案经过了,而另一个方案没有。保证“飞龙号”位于“零式”战斗机的攻击范围外,即 b|a|

输入格式

本题单个测试点内有多组数据。

第一行仅包含一个整数 T,表示数据组数。

对于每组数据仅包含一行:共三个整数 a,b,h,表示“飞龙号”的位置坐标和你驾驶的飞机目前的高度。

输出格式

对于每组数据,输出仅一行一个整数,表示答案对 998244353 取模后的结果。

样例一

input

3
2 756543 1
1 2 1
1 2 5

output

0
1
615

explanation

对于第一组数据,a=2b=756543h=1,当飞龙号位于 (2,756543) 时,你无论如何都无法从 1 高度机动到飞龙号位置。

对于第二组数据,a=1b=2h=1,当飞龙号位于 (1,2) 时,你有恰好一种方法可以攻击飞龙号,即先桶翻至 (1,1,0.5),再机动至 (1,2,0)

样例二~八

见附件下载,其中样例 2i1,2i 满足第 i 个子任务的限制。

限制与约定

本题采用捆绑测试,各个子任务之间开启所有合理的子任务依赖。

设单个测试点中每组数据的 h 的和为 h。对于所有数据,保证 1a,b,h106h106b|a|

  • Subtask 1(5 points):保证 h8
  • Subtask 2(15 points):保证 h500
  • Subtask 3(30 points):保证 h2×103
  • Subtask 4(50 points):无额外约束。

时间限制: 1s

空间限制: 512MB