从概率论到代码实战：深度解析CCPC"太阳轰炸"数学建模与C++实现

在算法竞赛的世界里，数学类题目往往是最令人又爱又怕的存在。"太阳轰炸"这道CCPC赛题完美展现了数学与编程的结合魅力——它需要选手理解几何概率、掌握组合数学、熟练模运算技巧，最终将抽象的概率公式转化为精确的代码实现。本文将彻底拆解这道经典题目，带你从数学原理推导到AC代码实现，特别聚焦那些让无数选手"踩坑"的模运算细节。

1. 题目理解与概率建模

"太阳轰炸"题目描述了一个简化的太空战场景：在一个半径为R的圆形区域内，攻击方会随机发射n枚炸弹，每枚炸弹的落点均匀分布在区域内。目标是一个半径为r的圆形防御护盾（r≤R），护盾只要被任意一枚炸弹击中就会被摧毁。我们需要计算护盾被摧毁的概率。

关键建模步骤 ：

1. 单次命中概率 ：计算单枚炸弹落在护盾区域内的概率

   • 大圆面积：πR²
   • 小圆面积：πr²
   • 单次命中概率 p = (πr²)/(πR²) = (r/R)²

2. 独立事件组合 ：n枚炸弹相当于n次独立重复试验

   • 护盾未被摧毁的概率 = (1-p)ⁿ
   • 被摧毁的概率 = 1 - (1-p)ⁿ

看起来简单的推导背后有几个重要假设：

• 炸弹落点完全随机且均匀分布
• 每次轰炸相互独立
• 边界条件处理（r=R或r=0的特殊情况）

2. 数学公式到可计算表达式

理论概率公式已经明确，但直接计算会遇到数值精度问题：

P = 1 - (1 - (r/R)²)^n

当R和r很大时，(r/R)²可能产生浮点精度损失。更稳妥的做法是保持分数形式，最后进行模运算：

P ≡ 1 - [(R² - r²)^n * inv(R^(2n))] mod MOD

其中inv表示模逆元。这需要以下组件：

1. 大数幂运算 ：快速计算R²、r²的n次幂
2. 组合数预处理 ：如果需要更复杂的概率模型
3. 模逆元计算 ：处理分数取模

3. 模运算的陷阱与解决方案

算法竞赛中常见模数1e9+7，但模运算有许多"坑"需要规避：

常见错误示例 ：

// 错误：直接对分数取模
int ans = 1 - pow(1 - (r*r)/(R*R), n); 
ans %= MOD;

正确做法分步解析 ：

1. 分子分母分离 ：

   long long numerator = (R*R - r*r) % MOD;
   long long denominator = power(R*R % MOD, n, MOD); // 快速幂
   

2. 分数取模公式 ：

   (a/b) mod MOD = (a * inv(b)) mod MOD
   

   其中inv(b)是b的模逆元

3. 完整概率计算 ：

   long long inv_denominator = inverse(denominator, MOD);
   long long P = (1 - power(numerator, n, MOD) * inv_denominator % MOD + MOD) % MOD;
   

特别注意 ：

• 减法后要加MOD再取模，避免负数
• 中间结果用long long防止溢出
• 多次取模保证数值范围

4. 完整AC代码实现与逐行解析

以下是结合上述分析的完整C++实现，包含关键注释：

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;

// 快速幂算法 (x^y) mod MOD
long long power(long long x, long long y, long long mod) {
    long long res = 1;
    x = x % mod;
    while (y > 0) {
        if (y & 1) res = (res * x) % mod;
        y = y >> 1;
        x = (x * x) % mod;
    }
    return res;
}

// 扩展欧几里得求模逆元
long long inverse(long long a, long long mod) {
    return power(a, mod-2, mod); // 费马小定理
}

int main() {
    long long R, r, n;
    cin >> R >> r >> n;
    
    // 计算分子 (R² - r²) mod MOD
    long long R_sq = (R % MOD) * (R % MOD) % MOD;
    long long r_sq = (r % MOD) * (r % MOD) % MOD;
    long long numerator = (R_sq - r_sq + MOD) % MOD;
    
    // 计算分母 R^(2n) mod MOD
    long long denominator = power(R_sq, n, MOD);
    
    // 计算逆元
    long long inv_denominator = inverse(denominator, MOD);
    
    // 计算 (numerator^n * inv_denominator) mod MOD
    long long term = power(numerator, n, MOD) * inv_denominator % MOD;
    
    // 最终概率 (1 - term + MOD) % MOD
    long long P = (1 - term + MOD) % MOD;
    
    cout << P << endl;
    return 0;
}

关键优化点 ：

1. 输入时直接取模，防止后续运算溢出
2. 使用快速幂算法高效计算大数次方
3. 费马小定理求模逆元（要求MOD是质数）
4. 每一步中间结果都严格控制在MOD范围内

5. 测试用例与边界条件验证

任何数学题目的代码都需要严谨的边界测试：

测试案例 (R, r, n)	预期输出	验证点
10 5 1	750000004	简单情况 (25%概率)
100 100 1000	1	r=R时必中
100 0 1000	0	r=0时必不中
1e9 1e8 1e18	999800029	大数测试
2 1 2	437500004	小数据验证

调试技巧 ：

• 打印中间变量检查计算步骤
• 验证特殊情况的数学期望
• 对拍：暴力计算小数据验证

6. 数学竞赛题的通用解题框架

通过这道题，我们可以总结数学竞赛题的通用解决流程：

1. 问题抽象化 ：将实际问题转化为数学模型
2. 公式推导 ：建立精确的数学表达式
3. 计算优化 ：将公式转化为可计算的离散形式
4. 代码实现 ：考虑语言特性和算法优化
5. 边界验证 ：测试各种极端情况

对于概率题目特别要注意：

• 概率值是否在[0,1]范围内
• 浮点精度是否足够
• 模运算下的等价转换

7. 扩展思考：不同概率模型的变种

"太阳轰炸"是基础几何概率模型，实际问题可能更复杂：

1. 非均匀分布 ：炸弹落点可能非均匀
2. 多护盾场景 ：多个防御护盾的联合概率
3. 部分摧毁 ：护盾有血量系统时的期望计算
4. 空间三维版 ：将圆形区域扩展为球体

例如，如果炸弹落点服从二维正态分布，我们需要重写概率密度函数并进行数值积分——这时蒙特卡洛模拟可能比解析解更实用。

8. 性能优化进阶技巧

当n极大时（如1e18），常规算法会超时。我们需要：

1. 欧拉降幂公式 ：当底数与模数互质时：

   a^b ≡ a^(b mod φ(MOD)) mod MOD
   

   其中φ是欧拉函数

2. 预处理技术 ：提前计算常用组合数

   const int MAXN = 1e6;
   long long fac[MAXN+1], inv_fac[MAXN+1];
   
   void precompute() {
       fac[0] = 1;
       for (int i = 1; i <= MAXN; i++) 
           fac[i] = fac[i-1] * i % MOD;
       
       inv_fac[MAXN] = inverse(fac[MAXN], MOD);
       for (int i = MAXN-1; i >= 0; i--)
           inv_fac[i] = inv_fac[i+1] * (i+1) % MOD;
   }
   

3. 卢卡斯定理 ：处理大组合数取模

9. 实际工程中的概率计算

虽然竞赛题使用精确计算，但工业级应用可能考虑：

1. 数值稳定性 ：使用对数空间计算极小概率

   log(P) = n * log(1 - (r/R)²)
   

2. 随机模拟 ：当解析解复杂时采用蒙特卡洛方法

   hits = 0
   for _ in range(simulations):
       x, y = random.uniform(-R, R), random.uniform(-R, R)
       if x*x + y*y <= r*r:
           hits += 1
   P = hits / simulations
   

3. 多精度库 ：使用GMP等库处理超大数

10. 从题目到算法的思维训练

解这类题目的核心能力在于：

1. 数学建模 ：将文字描述转化为数学公式
2. 离散化思维 ：将连续数学适配计算机处理
3. 边界感知 ：识别数值计算的危险区域
4. 模块化设计 ：将复杂问题分解为可验证的组件

建议训练方法：

• 从简单特例入手（如n=1）
• 手算小数据验证思路
• 编写测试生成器对拍
• 学习数论基础（模运算、同余定理）