Skip to main content

Advanced Math

Explore advanced mathematical concepts and algorithms for complex problem solving.

Fast Exponentiation​

Binary Exponentiation​

// Calculate a^b efficiently
long long power(long long base, long long exp) {
    long long result = 1;
    
    while (exp > 0) {
        if (exp & 1) {
            result *= base;
        }
        base *= base;
        exp >>= 1;
    }
    
    return result;
}

// With modulo
long long powerMod(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    
    while (exp > 0) {
        if (exp & 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp >>= 1;
    }
    
    return result;
}

Applications of Fast Exponentiation​

  • Modular inverse: Using Fermat's little theorem
  • Large number calculations: Avoiding overflow
  • Cryptography: RSA and other algorithms
  • Matrix exponentiation: For linear recurrences

Matrix Exponentiation​

Matrix Multiplication​

// Multiply two matrices
vector<vector<long long>> matrixMultiply(
    const vector<vector<long long>>& A,
    const vector<vector<long long>>& B,
    long long mod = 1e9 + 7
) {
    int n = A.size();
    int m = B[0].size();
    int p = B.size();
    
    vector<vector<long long>> result(n, vector<long long>(m, 0));
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (int k = 0; k < p; k++) {
                result[i][j] = (result[i][j] + (A[i][k] * B[k][j]) % mod) % mod;
            }
        }
    }
    
    return result;
}

Matrix Exponentiation​

// Calculate A^n using binary exponentiation
vector<vector<long long>> matrixPower(
    vector<vector<long long>> A,
    long long exp,
    long long mod = 1e9 + 7
) {
    int n = A.size();
    vector<vector<long long>> result(n, vector<long long>(n, 0));
    
    // Initialize result as identity matrix
    for (int i = 0; i < n; i++) {
        result[i][i] = 1;
    }
    
    while (exp > 0) {
        if (exp & 1) {
            result = matrixMultiply(result, A, mod);
        }
        A = matrixMultiply(A, A, mod);
        exp >>= 1;
    }
    
    return result;
}

Fibonacci & Linear Recurrence​

Fibonacci with Matrix Exponentiation​

// Calculate nth Fibonacci number using matrix exponentiation
long long fibonacciMatrix(long long n, long long mod = 1e9 + 7) {
    if (n <= 1) return n;
    
    // Transformation matrix: [F(n+1), F(n)] = [F(n), F(n-1)] * [[1,1],[1,0]]
    vector<vector<long long>> transform = {{1, 1}, {1, 0}};
    vector<vector<long long>> result = matrixPower(transform, n - 1, mod);
    
    return result[0][0];
}

General Linear Recurrence​

// Solve linear recurrence: f(n) = a1*f(n-1) + a2*f(n-2) + ... + ak*f(n-k)
long long linearRecurrence(
    vector<long long> coefficients,
    vector<long long> initialValues,
    long long n,
    long long mod = 1e9 + 7
) {
    int k = coefficients.size();
    if (n < k) return initialValues[n];
    
    // Build transformation matrix
    vector<vector<long long>> transform(k, vector<long long>(k, 0));
    for (int i = 0; i < k - 1; i++) {
        transform[i][i + 1] = 1;
    }
    for (int i = 0; i < k; i++) {
        transform[k - 1][i] = coefficients[k - 1 - i];
    }
    
    // Calculate transform^(n-k+1)
    vector<vector<long long>> power = matrixPower(transform, n - k + 1, mod);
    
    // Calculate result
    long long result = 0;
    for (int i = 0; i < k; i++) {
        result = (result + (power[0][i] * initialValues[i]) % mod) % mod;
    }
    
    return result;
}

Number Theory Problems​

Chinese Remainder Theorem​

// Solve system of congruences: x ≡ a[i] (mod m[i])
long long chineseRemainder(
    vector<long long> a,
    vector<long long> m
) {
    int n = a.size();
    long long M = 1;
    
    for (int i = 0; i < n; i++) {
        M *= m[i];
    }
    
    long long result = 0;
    for (int i = 0; i < n; i++) {
        long long Mi = M / m[i];
        long long Mi_inv = modInverse(Mi, m[i]);
        result = (result + (a[i] * Mi * Mi_inv) % M) % M;
    }
    
    return result;
}

Lucas Theorem​

// Calculate C(n, r) mod p where p is prime
long long lucasTheorem(long long n, long long r, long long p) {
    if (r > n) return 0;
    if (r == 0 || r == n) return 1;
    
    return (lucasTheorem(n / p, r / p, p) * 
            combination(n % p, r % p, p)) % p;
}

Wilson's Theorem​

// Check if p is prime using Wilson's theorem: (p-1)! ≡ -1 (mod p)
bool isPrimeWilson(long long p) {
    if (p <= 1) return false;
    if (p <= 3) return true;
    
    long long factorial = 1;
    for (long long i = 2; i < p; i++) {
        factorial = (factorial * i) % p;
    }
    
    return (factorial + 1) % p == 0;
}

Probability & Statistics​

Combinatorial Probability​

// Calculate probability of exactly k successes in n trials
double binomialProbability(int n, int k, double p) {
    if (k > n || k < 0) return 0.0;
    
    double result = 1.0;
    for (int i = 0; i < k; i++) {
        result *= (double)(n - i) / (i + 1) * p;
    }
    
    for (int i = k; i < n; i++) {
        result *= (1 - p);
    }
    
    return result;
}

Expected Value​

// Calculate expected value of a random variable
double expectedValue(vector<double> values, vector<double> probabilities) {
    double result = 0.0;
    for (int i = 0; i < values.size(); i++) {
        result += values[i] * probabilities[i];
    }
    return result;
}

Geometric Distribution​

// Calculate probability of first success on kth trial
double geometricProbability(int k, double p) {
    return pow(1 - p, k - 1) * p;
}

Advanced Algorithms​

Pollard's Rho Algorithm​

// Find a non-trivial factor of n
long long pollardRho(long long n) {
    if (n % 2 == 0) return 2;
    
    long long x = 2, y = 2, d = 1;
    
    while (d == 1) {
        x = (x * x + 1) % n;
        y = (y * y + 1) % n;
        y = (y * y + 1) % n;
        d = gcd(abs(x - y), n);
    }
    
    return d;
}

Miller-Rabin Primality Test​

// Probabilistic primality test
bool millerRabin(long long n, int k = 5) {
    if (n <= 1 || n == 4) return false;
    if (n <= 3) return true;
    
    long long d = n - 1;
    while (d % 2 == 0) {
        d /= 2;
    }
    
    for (int i = 0; i < k; i++) {
        long long a = 2 + rand() % (n - 4);
        long long x = powerMod(a, d, n);
        
        if (x == 1 || x == n - 1) continue;
        
        bool composite = true;
        for (int j = 0; j < d - 1; j++) {
            x = (x * x) % n;
            if (x == n - 1) {
                composite = false;
                break;
            }
        }
        
        if (composite) return false;
    }
    
    return true;
}

Optimization Techniques​

Fast Fourier Transform (FFT)​

// Multiply two polynomials using FFT
vector<complex<double>> fft(vector<complex<double>> a, bool invert) {
    int n = a.size();
    
    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1) {
            j ^= bit;
        }
        j ^= bit;
        
        if (i < j) {
            swap(a[i], a[j]);
        }
    }
    
    for (int len = 2; len <= n; len <<= 1) {
        double ang = 2 * M_PI / len * (invert ? -1 : 1);
        complex<double> wlen(cos(ang), sin(ang));
        
        for (int i = 0; i < n; i += len) {
            complex<double> w(1);
            for (int j = 0; j < len / 2; j++) {
                complex<double> u = a[i + j];
                complex<double> v = a[i + j + len / 2] * w;
                a[i + j] = u + v;
                a[i + j + len / 2] = u - v;
                w *= wlen;
            }
        }
    }
    
    if (invert) {
        for (complex<double>& x : a) {
            x /= n;
        }
    }
    
    return a;
}

Common Patterns​

  1. Matrix exponentiation for linear recurrences
  2. Fast exponentiation for large powers
  3. Modular arithmetic for overflow prevention
  4. Number theory for mathematical properties
  5. Probability for randomized algorithms

Performance Tips​

  • Use matrix exponentiation for linear recurrences
  • Precompute powers when possible
  • Use modular arithmetic to prevent overflow
  • Optimize with bit manipulation for powers of 2
  • Cache intermediate results for repeated calculations