modular.cpp

/*
Modular Arithmetic
Mathematical Foundation:
(a + b) mod m = ((a mod m) + (b mod m)) mod m
(a * b) mod m = ((a mod m) * (b mod m)) mod m
a^b mod m using fast exponentiation: O(log b)
Fermat's Little Theorem: a^(p-1) ≡ 1 (mod p) if p is prime
*/

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

// Fast Modular Exponentiation
// Related LeetCode Problems:
// 50. Pow(x, n)
// https://leetcode.com/problems/powx-n/
// 372. Super Pow
// https://leetcode.com/problems/super-pow/
// 1969. Minimum Non-Zero Product of the Array Elements
// https://leetcode.com/problems/minimum-non-zero-product-of-the-array-elements/
// 1735. Count Ways to Make Array With Product
// https://leetcode.com/problems/count-ways-to-make-array-with-product/
// 1830. Minimum Number of Operations to Make String Sorted
// https://leetcode.com/problems/minimum-number-of-operations-to-make-string-sorted/
// 1980. Find Unique Binary String
// https://leetcode.com/problems/find-unique-binary-string/
// 2320. Count Number of Ways to Place Houses
// https://leetcode.com/problems/count-number-of-ways-to-place-houses/
long long powmod(long long a, long long b, long long mod = 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;
}

// Modular Inverse using Fermat's Little Theorem (when mod is prime)
// Related LeetCode Problems:
// 1735. Count Ways to Make Array With Product
// https://leetcode.com/problems/count-ways-to-make-array-with-product/
// 1830. Minimum Number of Operations to Make String Sorted
// https://leetcode.com/problems/minimum-number-of-operations-to-make-string-sorted/
// 1904. The Number of Full Rounds You Have Played
// https://leetcode.com/problems/the-number-of-full-rounds-you-have-played/
// 1969. Minimum Non-Zero Product of the Array Elements
// https://leetcode.com/problems/minimum-non-zero-product-of-the-array-elements/
// 1359. Count All Valid Pickup and Delivery Options
// https://leetcode.com/problems/count-all-valid-pickup-and-delivery-options/
// 1569. Number of Ways to Reorder Array to Get Same BST
// https://leetcode.com/problems/number-of-ways-to-reorder-array-to-get-same-bst/
long long modinv(long long a, long long mod = MOD) {
    return powmod(a, mod - 2, mod);
}

// Modular Inverse using Extended Euclidean Algorithm
// Related LeetCode Problems:
// 365. Water and Jug Problem
// https://leetcode.com/problems/water-and-jug-problem/
// 1735. Count Ways to Make Array With Product
// https://leetcode.com/problems/count-ways-to-make-array-with-product/
// 1830. Minimum Number of Operations to Make String Sorted
// https://leetcode.com/problems/minimum-number-of-operations-to-make-string-sorted/
// 2607. Make K-Subarray Sums Equal
// https://leetcode.com/problems/make-k-subarray-sums-equal/
// 1969. Minimum Non-Zero Product of the Array Elements
// https://leetcode.com/problems/minimum-non-zero-product-of-the-array-elements/
long long extgcd(long long a, long long b, long long& x, long long& y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    long long x1, y1;
    long long g = extgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

long long modinvExt(long long a, long long mod = MOD) {
    long long x, y;
    long long g = extgcd(a, mod, x, y);
    return g == 1 ? (x % mod + mod) % mod : -1;
}

// Precomputed Factorials and Inverse Factorials
// Related LeetCode Problems:
// 1359. Count All Valid Pickup and Delivery Options
// https://leetcode.com/problems/count-all-valid-pickup-and-delivery-options/
// 1569. Number of Ways to Reorder Array to Get Same BST
// https://leetcode.com/problems/number-of-ways-to-reorder-array-to-get-same-bst/
// 1735. Count Ways to Make Array With Product
// https://leetcode.com/problems/count-ways-to-make-array-with-product/
// 1830. Minimum Number of Operations to Make String Sorted
// https://leetcode.com/problems/minimum-number-of-operations-to-make-string-sorted/
// 1916. Count Ways to Build Rooms in an Ant Colony
// https://leetcode.com/problems/count-ways-to-build-rooms-in-an-ant-colony/
// 2400. Number of Ways to Reach a Position After Exactly k Steps
// https://leetcode.com/problems/number-of-ways-to-reach-a-position-after-exactly-k-steps/
// 1131. Maximum of Absolute Value Expression
// https://leetcode.com/problems/maximum-of-absolute-value-expression/
// 1655. Distribute Repeating Integers
// https://leetcode.com/problems/distribute-repeating-integers/
class ModCombinatorics {
public:
    vector<long long> fact, inv_fact;
    int n;
    long long mod;
    
    ModCombinatorics(int n, long long mod = MOD) : n(n), mod(mod) {
        fact.resize(n + 1);
        inv_fact.resize(n + 1);
        
        fact[0] = 1;
        for (int i = 1; i <= n; i++)
            fact[i] = fact[i - 1] * i % mod;
        
        inv_fact[n] = modinv(fact[n], mod);
        for (int i = n - 1; i >= 0; i--)
            inv_fact[i] = inv_fact[i + 1] * (i + 1) % mod;
    }
    
    long long C(int n, int r) {
        if (r < 0 || r > n) return 0;
        return fact[n] * inv_fact[r] % mod * inv_fact[n - r] % mod;
    }
    
    long long P(int n, int r) {
        if (r < 0 || r > n) return 0;
        return fact[n] * inv_fact[n - r] % mod;
    }
};

// Matrix Exponentiation for recurrence relations
// Related LeetCode Problems:
// 509. Fibonacci Number
// https://leetcode.com/problems/fibonacci-number/
// 70. Climbing Stairs
// https://leetcode.com/problems/climbing-stairs/
// 552. Student Attendance Record II
// https://leetcode.com/problems/student-attendance-record-ii/
// 790. Domino and Tromino Tiling
// https://leetcode.com/problems/domino-and-tromino-tiling/
// 1220. Count Vowels Permutation
// https://leetcode.com/problems/count-vowels-permutation/
// 1137. N-th Tribonacci Number
// https://leetcode.com/problems/n-th-tribonacci-number/
// 1681. Minimum Incompatibility
// https://leetcode.com/problems/minimum-incompatibility/
// 2320. Count Number of Ways to Place Houses
// https://leetcode.com/problems/count-number-of-ways-to-place-houses/
struct Matrix {
    vector<vector<long long>> mat;
    int n;
    
    Matrix(int n) : n(n), mat(n, vector<long long>(n, 0)) {}
    
    Matrix operator*(const Matrix& other) const {
        Matrix res(n);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                for (int k = 0; k < n; k++)
                    res.mat[i][j] = (res.mat[i][j] + mat[i][k] * other.mat[k][j]) % MOD;
        return res;
    }
};

Matrix matpow(Matrix base, long long exp) {
    Matrix res(base.n);
    for (int i = 0; i < base.n; i++) res.mat[i][i] = 1; // identity
    
    while (exp > 0) {
        if (exp & 1) res = res * base;
        base = base * base;
        exp >>= 1;
    }
    return res;
}

// Fibonacci using Matrix Exponentiation
// Related LeetCode Problems:
// 509. Fibonacci Number
// https://leetcode.com/problems/fibonacci-number/
// 1137. N-th Tribonacci Number
// https://leetcode.com/problems/n-th-tribonacci-number/
// 70. Climbing Stairs
// https://leetcode.com/problems/climbing-stairs/
// 746. Min Cost Climbing Stairs
// https://leetcode.com/problems/min-cost-climbing-stairs/
// 118. Pascal's Triangle
// https://leetcode.com/problems/pascals-triangle/
long long fibonacci(long long n) {
    if (n <= 1) return n;
    Matrix base(2);
    base.mat = {{1, 1}, {1, 0}};
    Matrix result = matpow(base, n - 1);
    return result.mat[0][0];
}

// Discrete Logarithm - Baby Step Giant Step
// Related LeetCode Problems:
// 372. Super Pow
// https://leetcode.com/problems/super-pow/
// 50. Pow(x, n)
// https://leetcode.com/problems/powx-n/
// 1969. Minimum Non-Zero Product of the Array Elements
// https://leetcode.com/problems/minimum-non-zero-product-of-the-array-elements/
// 1735. Count Ways to Make Array With Product
// https://leetcode.com/problems/count-ways-to-make-array-with-product/
// 1830. Minimum Number of Operations to Make String Sorted
// https://leetcode.com/problems/minimum-number-of-operations-to-make-string-sorted/
long long discreteLog(long long a, long long b, long long m) {
    long long sq = sqrt(m) + 1;
    unordered_map<long long, long long> vals;
    
    long long cur = 1;
    for (long long i = 0; i < sq; i++) {
        if (vals.find(cur) == vals.end())
            vals[cur] = i;
        cur = cur * a % m;
    }
    
    long long factor = modinv(powmod(a, sq, m), m);
    long long gamma = b;
    for (long long i = 0; i < sq; i++) {
        if (vals.count(gamma))
            return i * sq + vals[gamma];
        gamma = gamma * factor % m;
    }
    return -1;
}

// Linear Congruence: ax ≡ b (mod m)
// Related LeetCode Problems:
// 365. Water and Jug Problem
// https://leetcode.com/problems/water-and-jug-problem/
// 2607. Make K-Subarray Sums Equal
// https://leetcode.com/problems/make-k-subarray-sums-equal/
// 1735. Count Ways to Make Array With Product
// https://leetcode.com/problems/count-ways-to-make-array-with-product/
// 1830. Minimum Number of Operations to Make String Sorted
// https://leetcode.com/problems/minimum-number-of-operations-to-make-string-sorted/
// 1969. Minimum Non-Zero Product of the Array Elements
// https://leetcode.com/problems/minimum-non-zero-product-of-the-array-elements/
vector<long long> solveLinearCongruence(long long a, long long b, long long m) {
    long long g = __gcd(a, m);
    if (b % g != 0) return {};
    
    a /= g; b /= g; m /= g;
    long long x0 = modinvExt(a, m) * b % m;
    
    vector<long long> solutions;
    for (long long i = 0; i < g; i++)
        solutions.push_back((x0 + i * m) % (m * g));
    
    return solutions;
}

// Quadratic Residue - Check if x² ≡ a (mod p) has solution
// Related LeetCode Problems:
// 367. Valid Perfect Square
// https://leetcode.com/problems/valid-perfect-square/
// 633. Sum of Square Numbers
// https://leetcode.com/problems/sum-of-square-numbers/
// 279. Perfect Squares
// https://leetcode.com/problems/perfect-squares/
// 365. Water and Jug Problem
// https://leetcode.com/problems/water-and-jug-problem/
// 2607. Make K-Subarray Sums Equal
// https://leetcode.com/problems/make-k-subarray-sums-equal/
long long jacobi(long long a, long long n) {
    if (a == 0) return 0;
    long long result = 1;
    if (a < 0) {
        a = -a;
        if (n % 4 == 3) result = -result;
    }
    
    while (a != 0) {
        while (a % 2 == 0) {
            a /= 2;
            if (n % 8 == 3 || n % 8 == 5) result = -result;
        }
        swap(a, n);
        if (a % 4 == 3 && n % 4 == 3) result = -result;
        a %= n;
    }
    return n == 1 ? result : 0;
}

bool isQuadraticResidue(long long a, long long p) {
    return jacobi(a, p) == 1;
}