信息学竞赛中的数学基础：数论、组合与概率

数学在信息学竞赛中的重要性

数学是信息学竞赛的基石。很多看似是编程问题的题目，本质上是数学问题。掌握必要的数学知识，不仅能帮助你快速找到解题思路，还能大大优化算法效率。

信息学竞赛中的数学知识体系

数论基础

1. 最大公约数（GCD）与最小公倍数（LCM）

欧几里得算法：

// 递归版本
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

// 迭代版本
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// 最小公倍数
int lcm(int a, int b) {
    return a / gcd(a, b) * b;  // 避免溢出
}

// 扩展欧几里得算法（求ax + by = gcd(a,b)的解）
int extgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    int g = extgcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
}

2. 素数判定与筛法

素数判定：

// 试除法 O(√n)
bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    }
    return true;
}

// Miller-Rabin素性测试（大数）
bool millerRabin(long long n) {
    if (n < 2) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0) return false;
    
    // 实现略，适用于大数素性判定
}

素数筛法：

// 埃拉托斯特尼筛法 O(nloglogn)
const int MAXN = 1000005;
bool isPrime[MAXN];
vector<int> primes;

void sieve() {
    fill(isPrime, isPrime + MAXN, true);
    isPrime[0] = isPrime[1] = false;
    
    for (int i = 2; i < MAXN; i++) {
        if (isPrime[i]) {
            primes.push_back(i);
            for (long long j = (long long)i * i; j < MAXN; j += i) {
                isPrime[j] = false;
            }
        }
    }
}

// 线性筛（欧拉筛）O(n)
void linearSieve() {
    fill(isPrime, isPrime + MAXN, true);
    isPrime[0] = isPrime[1] = false;
    
    for (int i = 2; i < MAXN; i++) {
        if (isPrime[i]) primes.push_back(i);
        
        for (int j = 0; j < primes.size() && i * primes[j] < MAXN; j++) {
            isPrime[i * primes[j]] = false;
            if (i % primes[j] == 0) break;  // 关键优化
        }
    }
}

3. 模运算与逆元

const int MOD = 1e9 + 7;

// 快速幂取模
long long powMod(long long a, long long b, long long mod) {
    long long res = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

// 费马小定理求逆元（mod为素数）
long long invMod(long long a, long long mod) {
    return powMod(a, mod - 2, mod);
}

// 扩展欧几里得求逆元
long long invModExt(long long a, long long mod) {
    long long x, y;
    long long g = extgcd(a, mod, x, y);
    if (g != 1) return -1;  // 逆元不存在
    return (x % mod + mod) % mod;
}

4. 欧拉函数

// 单个数的欧拉函数 O(√n)
int euler(int n) {
    int res = n;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            res = res / i * (i - 1);
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) res = res / n * (n - 1);
    return res;
}

// 筛法求欧拉函数
int phi[MAXN];
void eulerSieve() {
    for (int i = 1; i < MAXN; i++) phi[i] = i;
    
    for (int i = 2; i < MAXN; i++) {
        if (phi[i] == i) {  // i是素数
            for (int j = i; j < MAXN; j += i) {
                phi[j] = phi[j] / i * (i - 1);
            }
        }
    }
}

组合数学

1. 排列组合计算

// 方法1：杨辉三角递推
const int MAXN = 1005;
long long C[MAXN][MAXN];

void initCombination() {
    C[0][0] = 1;
    for (int i = 1; i < MAXN; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
        }
    }
}

// 方法2：费马小定理（需要预处理阶乘）
long long fact[MAXN], invFact[MAXN];

void initFactorial() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        fact[i] = fact[i-1] * i % MOD;
    }
    invFact[MAXN-1] = invMod(fact[MAXN-1], MOD);
    for (int i = MAXN-2; i >= 0; i--) {
        invFact[i] = invFact[i+1] * (i+1) % MOD;
    }
}

long long nCr(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fact[n] * invFact[r] % MOD * invFact[n-r] % MOD;
}

// 方法3：Lucas定理（大组合数取模）
long long lucas(long long n, long long m, long long p) {
    if (m == 0) return 1;
    return nCr(n % p, m % p) * lucas(n / p, m / p, p) % p;
}

2. 容斥原理

经典问题：错排问题

// n个元素的错排数：D(n) = (n-1) * (D(n-1) + D(n-2))
long long derangement[MAXN];

void initDerangement() {
    derangement[0] = 1;
    derangement[1] = 0;
    for (int i = 2; i < MAXN; i++) {
        derangement[i] = (i - 1) * (derangement[i-1] + derangement[i-2]) % MOD;
    }
}

容斥原理应用：

// 求1到n中与m互质的数的个数
int coprimeCount(int n, int m) {
    vector<int> factors;
    int temp = m;
    
    // 分解质因数
    for (int i = 2; i * i <= temp; i++) {
        if (temp % i == 0) {
            factors.push_back(i);
            while (temp % i == 0) temp /= i;
        }
    }
    if (temp > 1) factors.push_back(temp);
    
    // 容斥原理
    int result = n;
    int size = factors.size();
    for (int mask = 1; mask < (1 << size); mask++) {
        int product = 1, bits = 0;
        for (int i = 0; i < size; i++) {
            if (mask & (1 << i)) {
                product *= factors[i];
                bits++;
            }
        }
        if (bits & 1) {
            result -= n / product;
        } else {
            result += n / product;
        }
    }
    
    return result;
}

3. 卡特兰数

// 卡特兰数：C(n) = C(2n,n) / (n+1)
// 应用：括号匹配、出栈序列、二叉搜索树等

long long catalan[MAXN];

void initCatalan() {
    catalan[0] = catalan[1] = 1;
    
    // 递推公式1
    for (int i = 2; i < MAXN; i++) {
        catalan[i] = catalan[i-1] * 2 * (2*i - 1) / (i + 1);
    }
    
    // 递推公式2
    for (int i = 2; i < MAXN; i++) {
        catalan[i] = 0;
        for (int j = 0; j < i; j++) {
            catalan[i] = (catalan[i] + catalan[j] * catalan[i-1-j]) % MOD;
        }
    }
}

概率与期望

1. 基础概率计算

// 投掷n次硬币，恰好k次正面的概率
double coinProbability(int n, int k) {
    return C[n][k] * pow(0.5, n);
}

// 生日悖论：n个人中至少两人生日相同的概率
double birthdayParadox(int n) {
    if (n > 365) return 1.0;
    double prob = 1.0;
    for (int i = 0; i < n; i++) {
        prob *= (365.0 - i) / 365.0;
    }
    return 1.0 - prob;
}

2. 期望DP

// 投掷骰子，期望多少次得到和为n
double diceExpectation(int n) {
    vector<double> dp(n + 1, 0);
    
    for (int i = 1; i <= n; i++) {
        dp[i] = 1;  // 本次投掷
        for (int j = 1; j <= 6 && j < i; j++) {
            dp[i] += dp[i - j] / 6.0;
        }
        dp[i] = dp[i] * 6.0 / min(i, 6);
    }
    
    return dp[n];
}

// 随机游走：从0开始，每次+1或-1，到达n的期望步数
double randomWalk(int n) {
    // E[i] = 1 + 0.5 * E[i-1] + 0.5 * E[i+1]
    // 解得：E[i] = 2*i - E[i-1]
    vector<double> E(n + 1);
    E[0] = 0;
    E[1] = 1;
    for (int i = 2; i <= n; i++) {
        E[i] = 2 * E[i-1] - E[i-2] + 2;
    }
    return E[n];
}

中国剩余定理

// 解同余方程组：x ≡ a[i] (mod m[i])
// 要求m[i]两两互质

long long CRT(vector<long long>& a, vector<long long>& m) {
    int n = a.size();
    long long M = 1, result = 0;
    
    for (int i = 0; i < n; i++) M *= m[i];
    
    for (int i = 0; i < n; i++) {
        long long Mi = M / m[i];
        long long ti = invModExt(Mi, m[i]);
        result = (result + a[i] * Mi * ti) % M;
    }
    
    return (result + M) % M;
}

博弈论基础

Nim游戏

// n堆石子，每次可以从一堆取任意个
// 先手必胜条件：所有堆的异或和不为0

bool nimGame(vector<int>& piles) {
    int xorSum = 0;
    for (int pile : piles) {
        xorSum ^= pile;
    }
    return xorSum != 0;
}

// SG函数（Sprague-Grundy定理）
int sg[MAXN];
bool vis[MAXN];

int getSG(int n) {
    if (sg[n] != -1) return sg[n];
    
    memset(vis, false, sizeof(vis));
    
    // 计算所有后继状态的SG值
    for (int i = 1; i <= n/2; i++) {
        vis[getSG(i) ^ getSG(n - i)] = true;
    }
    
    // MEX运算
    for (int i = 0; ; i++) {
        if (!vis[i]) {
            return sg[n] = i;
        }
    }
}

数学问题实战技巧

常见优化技巧

经典数学题目

题目分类推荐

总结

数学是信息学竞赛的重要基础，掌握数学知识需要：

1. 系统学习：按照知识体系逐步深入
2. 理解本质：不要死记公式，理解推导过程
3. 灵活应用：识别题目中的数学模型
4. 优化技巧：预处理、取模、防溢出
5. 多做练习：数学题需要大量练习培养直觉

记住，数学不是信息学竞赛的全部，但没有数学基础，很难在竞赛中走得更远。打好数学基础，你的算法之路会更加顺畅！