题目分析

这是一个在特殊坐标系下的最大独立集计数问题。

关键观察

1. 坐标系特性：x轴与y轴夹角60度，这是一个斜角坐标系
2. 点集筛选：
   • 横纵坐标不全为偶数（排除全偶点）
   • 在三个方向上有范围限制：x∈[-2a+1, 2a-1], y∈[-2b+1, 2b-1], x+y∈[-2c+1, 2c-1]
3. 相邻关系：每个点有6个相邻点，形成六边形网格

解题思路

第一步：坐标系转换

将60度坐标系转换为更易处理的形式。考虑坐标变换：

u = x
v = x + 2y

这样相邻关系会变成更规则的网格结构。

第二步：奇偶性分析

由于只排除"横纵坐标全为偶数"的点，可以将所有点按坐标奇偶性分为4类：

• (奇, 奇)
• (奇, 偶)
• (偶, 奇)
• (偶, 偶) ← 被排除

实际上，这个六边形网格是一个二分图，可以按(u+v)的奇偶性划分。

第三步：最大独立集

在二分图中，最大独立集大小 = 总点数 - 最小点覆盖大小 根据König定理，在二分图中最小点覆盖 = 最大匹配

因此问题转化为：

1. 计算满足条件的点数
2. 计算这个二分图的最大匹配
3. 计算达到最大匹配的方案数

第四步：三维范围处理

三个不等式定义了一个六边形区域：

• -2a+1 ≤ x ≤ 2a-1
• -2b+1 ≤ y ≤ 2b-1
• -2c+1 ≤ x+y ≤ 2c-1

这可以看作三维空间中的长方体约束。

算法框架

对于每组数据(a,b,c)：

1. 计算总点数：通过容斥原理计算满足三个范围约束且不全为偶数的点数
2. 建立二分图模型：按(x+y)的奇偶性划分点集
3. 计算最大匹配：在特殊网格结构中，最大匹配有组合表达式
4. 计算方案数：使用组合数学方法计算达到最大匹配的染色方案数

复杂度分析

• 直接枚举所有点：O(abc) 不可行（最大10^18）
• 需要数学推导出闭式解或递推公式
• 目标复杂度：O(1) 或 O(log n) 每组数据

实现要点

1. 利用对称性简化问题
2. 对a,b,c进行排序，假设a≤b≤c
3. 分类讨论不同情况：
   • 当约束很紧时（六边形很小）
   • 当约束较松时（接近完整网格）
4. 使用模运算处理大数

结论

这道题需要深厚的组合数学功底，通过巧妙的坐标变换和奇偶性分析，将几何问题转化为图论问题，再通过组合计数得到最终解。是ZJOI中的经典难题。