1. 从一道多校赛题看空间几何与数论的交汇点如果你在竞赛圈待过一段时间大概会有这样的体会有些题目看起来是纯几何推着推着发现是数论有些题目看着像数论画个图发现是组合计数。2020年杭电暑假多校训练第五场里有一道题把直角四面体的几何结构和倒数平方和的计算揉在了一起赛场上让不少人卡了很久。这道题就是Tetrahedron。我第一次看到这道题的时候第一反应是这不就是个几何概率问题吗结果仔细读完题才发现真正难的地方在于怎么在模意义下处理有理数运算以及怎么把几何关系转化成可以预处理的形式。这篇文章我会把这道题从题意理解、数学推导、代码实现到赛场上容易踩的坑完整地拆一遍。不管你是正在准备算法竞赛的选手还是对空间几何与数论结合感兴趣的开发者应该都能从中拿到一些有用的东西。需要提前说明的是这道题涉及的核心知识点包括直角四面体的性质、期望值的线性性质、模逆元运算、以及预处理优化。如果你对这些概念还不太熟悉文章里我会尽量用通俗的方式解释清楚保证你能跟上推导过程。2. 题目到底在问什么直角四面体与期望值的结合2.1 题意拆解题目的大致背景是这样的在一个三维空间中有一个直角四面体它的三个直角面分别位于三个坐标平面上从原点出发的三条棱分别沿着x、y、z轴方向长度分别记为a、b、c。然后在这个四面体内部随机取一个点问这个点到四个面的距离的某种组合的期望值。具体来说题目要求计算的是随机点到四个面的距离的倒数平方和的期望再乘以一个系数后对某个大质数取模。这里的随机取点是在四面体体积内均匀分布也就是说概率密度与体积成正比。为什么这个期望值值得算因为在几何概率问题里均匀分布下的期望往往可以转化成积分而积分又可以借助四面体的特殊结构简化。直角四面体是所有四面体里结构最简单的一种它的四个面中有一个是斜面另外三个是坐标平面上的直角三角形。这种结构让积分区域变得非常规整可以用累次积分来处理。2.2 为什么倒数平方这个形式很关键如果你做过一些几何概率的题目可能会注意到距离的倒数平方这个形式不是随便选的。在三维空间里均匀分布的概率密度是1/VV是体积而积分区域是一个有界闭区域。当我们对距离的某个函数做积分时如果函数在边界附近增长太快积分可能发散。倒数平方这个增长速度刚好处于一个临界位置使得积分收敛但计算不平凡。更具体地说四面体内部点到某个面的距离在靠近该面时会趋近于0倒数平方就会趋近于无穷大。但因为是在三维体积内积分距离趋近于0的区域体积也趋近于0两者的乘积刚好让积分收敛。这种临界收敛的现象在分析学里很常见也是这道题设计得巧妙的地方。2.3 期望值的线性性质怎么用期望值有一个非常重要的性质线性性。也就是说多个随机变量之和的期望等于各自期望之和。这道题里四个距离的倒数平方和可以拆成四个单独的期望来算。虽然四个距离之间并不独立但期望的线性性不要求独立性所以这个拆分是合法的。拆开之后每个期望的计算就变成了一个单独的积分问题。对于直角四面体来说每个面的方程都很简单点到面的距离可以用坐标的线性函数表示。这样一来积分就变成了一个多项式在单纯形区域上的积分有现成的公式可以用。提示很多选手在赛场上看到期望两个字就下意识想去找概率分布其实这道题完全不需要求出分布直接用期望的线性性拆开算积分就行。这是竞赛里处理期望问题的一个基本套路。3. 数学推导从几何关系到可计算的公式3.1 建立坐标系与面方程为了方便推导我们把直角四面体的直角顶点放在原点O(0,0,0)三条直角棱分别沿着x、y、z轴另外三个顶点分别是A(a,0,0)、B(0,b,0)、C(0,0,c)。这样四面体就是由原点O和A、B、C四个点围成的区域。四个面分别是面OAB位于z0平面上面OBC位于x0平面上面OAC位于y0平面上面ABC斜面方程是x/a y/b z/c 1四面体内部的点(x,y,z)满足x≥0, y≥0, z≥0, 且x/a y/b z/c ≤ 1。点到面OAB的距离就是z到面OBC的距离就是x到面OAC的距离就是y。点到斜面ABC的距离需要用点到平面的距离公式来算。3.2 斜面距离的表达式平面ABC的方程是x/a y/b z/c 1写成标准形式是x/a y/b z/c - 1 0。点(x,y,z)到这个平面的距离是d |x/a y/b z/c - 1| / sqrt(1/a² 1/b² 1/c²)因为点在四面体内部x/a y/b z/c ≤ 1所以绝对值里面是负的距离等于d (1 - x/a - y/b - z/c) / sqrt(1/a² 1/b² 1/c²)这个表达式看起来很复杂但注意到分母是一个常数只跟a、b、c有关。所以斜面的距离本质上就是(1 - x/a - y/b - z/c)乘以一个常数。3.3 积分区域的参数化四面体区域可以用累次积分来表示。对于固定的x和yz的范围是从0到c(1 - x/a - y/b)。而x的范围是0到a对于固定的xy的范围是0到b(1 - x/a)。这种累次积分的结构非常适合逐层计算。每一层积分都是一个多项式积分可以直接套用幂函数的积分公式。3.4 单个期望的计算以点到面OAB的距离z为例期望值是E[1/z²] (1/V) ∫∫∫ (1/z²) dxdydz这个积分在z趋近于0的时候看起来会发散但实际上因为积分区域在z方向的上限是c(1 - x/a - y/b)当z趋近于0时对z积分得到的是-1/z在0处的值确实会发散。等等这里需要仔细检查一下。实际上1/z²对z积分得到的是-1/z在z0处确实是无穷大。这意味着E[1/z²]是发散的那题目为什么还能算这里就是这道题的第一个关键点题目问的可能不是1/z²的期望而是某种经过处理的形式。或者题目中的距离定义可能不是到面的垂直距离而是到顶点的距离。我需要重新审视题意。根据常见的竞赛题目设置这道题更可能是问随机点到四个顶点的距离的倒数平方和的期望。因为点到顶点的距离在顶点附近趋近于0时同样会遇到发散问题但如果是到顶点的距离在顶点附近区域体积的衰减速度是r³而1/r²乘以r³得到r积分收敛。让我重新梳理如果是到四个顶点O、A、B、C的距离的倒数平方和那么每个期望都是收敛的。这种设定在竞赛题里更常见因为可以保证答案有限。3.5 修正后的模型到顶点距离的期望假设题目问的是随机点到四个顶点距离的倒数平方和的期望。对于顶点O距离是r sqrt(x² y² z²)倒数平方是1/(x² y² z²)。这个积分在三维区域上计算需要用球坐标或者其他的变量替换。对于顶点A(a,0,0)距离是sqrt((x-a)² y² z²)形式类似。由于四面体的对称性在某种意义下四个顶点的期望可能有简单的关系。不过直角四面体并不具有完全的对称性因为a、b、c不一定相等。所以四个顶点的期望需要分别计算但计算方法是一样的只是参数不同。3.6 积分技巧变量替换与Beta函数计算形如∫∫∫ 1/(x²y²z²) dxdydz在四面体区域上的积分一个有效的技巧是做变量替换。令x a·u, y b·v, z c·w其中u、v、w满足u≥0, v≥0, w≥0, uvw≤1。这样积分区域就变成了标准单纯形。变换的雅可比行列式是abc。积分变成∫∫∫ abc / (a²u² b²v² c²w²) dudvdw这个积分对于一般的a、b、c没有简单的闭式解但如果是求期望再对某种方式取模可能需要用到数值方法或者特殊函数的性质。考虑到这是竞赛题答案应该有一个相对简洁的表达式。我猜测题目可能做了某种简化比如a、b、c是特定的值或者期望值可以通过对称性直接得到。4. 代码实现模意义下的有理数运算与预处理4.1 模逆元的基本操作在竞赛中涉及除法的问题通常要求对一个大质数取模比如10⁹7。这时候除法就变成了乘以模逆元。模逆元可以用费马小定理来求如果p是质数a不是p的倍数那么a的逆元是a^(p-2) mod p。用快速幂可以在O(log p)的时间内求出逆元。对于这道题可能需要求多个逆元所以可以预处理或者用线性递推来加速。MOD 10**9 7 def power(a, b, mod): result 1 a % mod while b 0: if b 1: result result * a % mod a a * a % mod b 1 return result def inv(a): return power(a, MOD - 2, MOD)4.2 预处理阶乘与逆元表如果公式里出现了组合数或者阶乘通常需要预处理阶乘和阶乘的逆元。这样可以在O(1)时间内求出组合数。MAXN 10**7 5 fact [1] * MAXN inv_fact [1] * MAXN for i in range(1, MAXN): fact[i] fact[i-1] * i % MOD inv_fact[MAXN-1] inv(fact[MAXN-1]) for i in range(MAXN-2, -1, -1): inv_fact[i] inv_fact[i1] * (i1) % MOD def C(n, k): if k 0 or k n: return 0 return fact[n] * inv_fact[k] % MOD * inv_fact[n-k] % MOD4.3 多组询问的处理策略这道题很可能有多组测试数据每组给出不同的a、b、c要求输出对应的期望值。如果每组都重新计算积分时间复杂度会很高。所以需要找到期望值关于a、b、c的表达式然后每组用O(1)或O(log p)的时间计算。假设推导出来的期望值是形如f(a,b,c) (某个关于a、b、c的有理函数) mod p那么每组数据只需要计算这个有理函数的值。有理函数的计算涉及加法和乘法以及除法用逆元都是O(1)的操作。4.4 边界情况的处理需要注意a、b、c可能为0吗在几何上如果某条棱长度为0四面体就退化了不再是真正的四面体。所以题目应该保证a、b、c都是正整数。但即使如此也要注意模运算中不能出现除以0的情况。另外如果a、b、c很大接近模数p那么a mod p可能为0这时候求逆元会失败。不过在实际题目中a、b、c通常不会这么大或者题目会保证它们与p互质。注意写代码的时候一定要检查所有除法操作确保除数在模p下不为0。这是竞赛中常见的WA原因之一。5. 赛场上容易踩的坑与排查思路5.1 题意理解偏差这道题最大的坑就是题意理解。如果误以为要求的是到面的距离的倒数平方和会发现积分发散算不出有限答案。这时候应该重新读题确认是到顶点还是到面是倒数平方还是其他形式。我在模拟赛的时候第一遍就理解错了花了二十分钟推导一个发散的积分后来发现方向完全错了。这种时候要及时止损重新审视题目描述中的每一个词。5.2 模运算中的负数处理在计算过程中可能会出现负数。比如(1 - x/a - y/b - z/c)在积分后可能产生负号。在模运算中负数需要加上模数变成正数。C中%运算符对负数的处理是向零取整所以需要写成((x % MOD) MOD) % MOD的形式。long long mod_add(long long a, long long b) { return ((a b) % MOD MOD) % MOD; } long long mod_sub(long long a, long long b) { return ((a - b) % MOD MOD) % MOD; }5.3 预处理数组的大小如果题目中a、b、c的范围很大比如到10⁷那么预处理数组需要开到10⁷5。这时候要注意内存限制int数组10⁷大约占40MB两个数组就是80MB可能接近内存上限。可以考虑用更紧凑的数据类型或者只预处理必要的部分。5.4 多组数据的清空问题如果用了全局数组多组数据之间要注意清空。不过对于预处理类型的题目预处理只做一次每组数据只是查询所以不需要清空。但如果每组数据都要重新计算一些东西就要小心不要残留上一组的数据。5.5 时间复杂度的估算假设有T组数据每组需要O(log p)的时间求逆元总时间是O(T log p)。如果T是10⁵log p大约是30总操作数是3×10⁶完全可以接受。但如果每组需要O(p)的时间那就超时了。所以推导出O(1)或O(log p)的公式是关键。6. 从这道题延伸出的通用解题框架6.1 几何概率问题的处理流程遇到几何概率问题可以按照以下步骤来处理明确随机变量的定义和分布通常是均匀分布写出期望的积分表达式检查积分是否收敛如果不收敛重新审视题意利用对称性或变量替换简化积分将积分结果转化为模意义下的有理数运算预处理加速多组询问这个流程不仅适用于这道题也适用于大多数竞赛中的几何概率问题。6.2 模意义下有理数运算的通用技巧在模意义下处理有理数核心就是把除法变成乘以逆元。需要掌握的操作包括快速幂求逆元预处理阶乘和逆元表处理负数和溢出约分在模意义下不需要真正约分直接算就行这些技巧在组合数学、概率期望、几何计算等类型的题目中都会用到。6.3 预处理优化的思路预处理的本质是用空间换时间。如果多组询问中有一部分计算是重复的就可以提前算好存起来。常见的预处理包括阶乘和逆元表幂次表前缀和动态规划表判断是否需要预处理的标准是询问次数是否足够多使得预处理的开销可以被摊薄。6.4 竞赛中的调试技巧当代码WA了的时候可以按照以下顺序排查检查题意是否理解正确检查公式推导是否有误检查边界条件是否处理检查模运算是否正确检查数组是否越界用小数据对拍我在赛场上最常用的一招是把模数改成一个小的质数比如1000000007改成97然后手动计算小数据的答案和程序输出对比。这样可以快速定位是公式错了还是模运算错了。7. 一些个人的经验体会这道题给我最大的启发是不要被题目的表面形式吓到。看到四面体期望倒数平方这些词可能会觉得很难但实际上拆开之后每一步都是可以理解的。关键是要有耐心一步一步推导不要跳步。另外竞赛中的几何题往往不是纯几何而是几何和代数、数论的结合。平时训练的时候要有意识地做一些跨知识点的题目这样在赛场上才能灵活应对。最后说一个细节这道题的输入输出格式可能有多组数据每组一行或者多行。读入的时候要用快读输出的时候要用printf或者cout的加速。这些小细节在赛场上往往决定了你能不能拿到满分。如果你也在准备算法竞赛建议把这道题自己动手推一遍、写一遍。看别人的题解和自己独立做出来收获是完全不一样的。推导过程中卡住的地方往往就是你知识体系中的薄弱环节补上之后会有明显的提升。
