Modulo Arithmetic

Banyak soal kompetisi meminta jawaban “modulo 10⁹+7” untuk mencegah overflow dan menyederhanakan pembandingan jawaban. Sayangnya, modulo bukan sekadar “ambil sisa” — operasi modulo punya properti yang harus dipahami, terutama saat melakukan perkalian besar, pengurangan yang bisa menghasilkan negatif, dan pembagian (yang membutuhkan modular inverse). Pada Chapter ini kita akan menurunkan properti kunci modulo dan mempraktikkannya pada perhitungan kombinatorial sederhana.

Properti Dasar Modulo #

Aturan #

Untuk sembarang bilangan bulat a, b dan m > 0:

text
(a + b) mod m = ((a mod m) + (b mod m)) mod m        (1) penjumlahan
(a - b) mod m = ((a mod m) - (b mod m) + m) mod m     (2) pengurangan (hati-hati negatif!)
(a · b) mod m = ((a mod m) · (b mod m)) mod m         (3) perkalian
a^k mod m     = (...((a mod m) · a) mod m · ... · a) mod m   (4) pangkat (iteratif)

Mekanisme: Mengapa Modulo Diperlukan #

long long (64-bit) dapat menampung hingga ~1,8 × 10¹⁹. Perkalian dua bilangan 10⁹ menghasilkan 10¹⁸ — masih muat. Tetapi perkalian tiga bilangan 10⁹ menghasilkan 10²⁷ — overflow. Modulo setelah setiap operasi memastikan nilai tetap kecil.

Pola Penting: Pengurangan Negatif #

Aturan #

Dalam C++, -5 % 3 bisa menghasilkan -2 (bukan 1 seperti yang diharapkan secara matematis). Untuk mendapatkan hasil non-negatif yang konsisten, gunakan formula (a - b % m + m) % m.

Kode: Pengurangan Modulo yang Aman #

cpp
#include <iostream>

long long add_mod(long long a, long long b, long long m) {
    return ((a % m) + (b % m)) % m;
}

long long sub_mod(long long a, long long b, long long m) {
    return ((a % m) - (b % m) + m) % m;
}

long long mul_mod(long long a, long long b, long long m) {
    return ((a % m) * (b % m)) % m;
}

int main() {
    long long m = 1'000'000'007;
    std::cout << "add_mod(10, 20, m) = " << add_mod(10, 20, m) << '\n';
    std::cout << "sub_mod(10, 20, m) = " << sub_mod(10, 20, m) << '\n';
    std::cout << "sub_mod(20, 10, m) = " << sub_mod(20, 10, m) << '\n';
    std::cout << "mul_mod(123456789, 987654321, m) = "
              << mul_mod(123456789LL, 987654321LL, m) << '\n';

    // Demonstrasi overflow tanpa modulo
    long long a = 1'000'000'000LL;
    long long b = 1'000'000'000LL;
    long long c = 1'000'000'000LL;
    std::cout << "a*b tanpa mod = " << a * b << '\n';          // masih muat di long long
    std::cout << "a*b*c tanpa mod = " << a * b * c << '\n';    // overflow!
    std::cout << "a*b*c dengan mod = "
              << mul_mod(mul_mod(a, b, m), c, m) << '\n';
    return 0;
}

Output yang Dihasilkan:

text
add_mod(10, 20, m) = 30
sub_mod(10, 20, m) = 999999997
sub_mod(20, 10, m) = 10
mul_mod(123456789, 987654321, m) = 259106859
a*b tanpa mod = 1000000000000000000
a*b*c tanpa mod = -6930898827444486144
a*b*c dengan mod = 999999664

Baris return ((a % m) + (b % m)) % m;: tambahkan sisa-sisa modulo, lalu modulo lagi. Mencegah overflow di penjumlahan (meski penjumlahan jarang overflow).
Baris return ((a % m) - (b % m) + m) % m;: tambahkan m sebelum modulo untuk menangani hasil negatif. Tanpa + m, hasil bisa negatif.
Baris return ((a % m) * (b % m)) % m;: kunci untuk perkalian besar. Modulo dulu masing-masing operand, baru kali, baru modulo lagi.
Hasil sub_mod(10, 20, m) = 999999997: (10 - 20 + m) % m = m - 10 = 999999997. Sesuai.
Hasil mul_mod(123456789, 987654321, m) = 259106859: perkalian ~1.2 × 10¹⁷ dimodulo m. Tanpa modulo, hasil masih muat di long long (1.2 × 10¹⁷ < 1.8 × 10¹⁹).
Hasil a*b tanpa mod = 10^18: masih muat di long long (max ~1.8 × 10¹⁹).
Hasil a*b*c tanpa mod = -6.9 × 10^18: OVERFLOW! Hasil 10^27 melebihi long long, terbungkus ke nilai negatif. Ini adalah bug klasik.
Hasil a*b*c dengan mod = 999999664: dengan modulo di setiap langkah, hasil benar 10^27 mod 1e9+7. Sesuai.

Pola: Perkalian Modular dengan `__int128` #

Aturan #

Untuk m hingga 2^62, perkalian (a % m) * (b % m) bisa overflow bila m mendekati 2^62. Gunakan __int128 (ekstensi GCC) untuk menampung sementara produk 128-bit, lalu modulo.

Kode: Perkalian Modular dengan __int128 #

cpp
#include <iostream>

long long mul_mod_128(long long a, long long b, long long m) {
    __int128 prod = (__int128)a * b;
    return (long long)(prod % m);
}

int main() {
    long long m = 1'000'000'007LL * 1'000'000'007LL;  // m ~ 10^18
    std::cout << "m = " << m << '\n';
    long long a = m - 1;  // ~10^18
    long long b = m - 1;
    std::cout << "(m-1)*(m-1) mod m = " << mul_mod_128(a, b, m) << '\n';
    std::cout << "Expected: ((m-1)^2) mod m = ((-1)^2) mod m = 1\n";
    return 0;
}

Output yang Dihasilkan:

text
m = 1000000014000000049
(m-1)*(m-1) mod m = 1
Expected: ((m-1)^2) mod m = ((-1)^2) mod m = 1

Baris __int128 prod = (__int128)a * b;: cast salah satu operand ke __int128 (128-bit) sebelum perkalian. Hasil produk disimpan di 128-bit, tidak overflow.
Baris return (long long)(prod % m);: modulo dengan m (yang bisa hingga 2^62), lalu cast balik ke long long.
Hasil (m-1)*(m-1) mod m = 1: (m-1) ≡ -1 (mod m), sehingga (m-1)² ≡ 1 (mod m). Sesuai.

Aplikasi: Binomial Coefficient Modulo #

Aturan #

Hitung C(n, k) mod m dengan n, k hingga 10⁶. Pendekatan: precompute faktorial fact[i] dan inverse faktorial invfact[i] modulo m. Lalu C(n, k) = fact[n] · invfact[k] · invfact[n-k] mod m.

Kode: Binomial dengan Precompute #

cpp
#include <iostream>
#include <vector>

const long long MOD = 1'000'000'007;

long long fast_pow(long long b, long long k, long long m) {
    long long r = 1; b %= m;
    while (k > 0) {
        if (k & 1) r = (r * b) % m;
        b = (b * b) % m;
        k >>= 1;
    }
    return r;
}

int main() {
    int N = 10;
    std::vector<long long> fact(N + 1), invfact(N + 1);
    fact[0] = 1;
    for (int i = 1; i <= N; ++i) fact[i] = (fact[i-1] * i) % MOD;
    invfact[N] = fast_pow(fact[N], MOD - 2, MOD);
    for (int i = N - 1; i >= 0; --i) invfact[i] = (invfact[i+1] * (i+1)) % MOD;

    auto C = [&](int n, int k) -> long long {
        if (k < 0 || k > n) return 0;
        return fact[n] * invfact[k] % MOD * invfact[n-k] % MOD;
    };

    for (int n = 0; n <= 5; ++n) {
        for (int k = 0; k <= n; ++k) {
            std::cout << "C(" << n << "," << k << ")=" << C(n, k) << ' ';
        }
        std::cout << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text
C(0,0)=1 
C(1,0)=1 C(1,1)=1 
C(2,0)=1 C(2,1)=2 C(2,2)=1 
C(3,0)=1 C(3,1)=3 C(3,2)=3 C(3,3)=1 
C(4,0)=1 C(4,1)=4 C(4,2)=6 C(4,3)=4 C(4,4)=1 
C(5,0)=1 C(5,1)=5 C(5,2)=10 C(5,3)=10 C(5,4)=5 C(5,5)=1 

Baris fact[0] = 1;: base case — 0! = 1.
Baris fact[i] = (fact[i-1] * i) % MOD;: precompute i! secara iteratif. O(N).
Baris invfact[N] = fast_pow(fact[N], MOD - 2, MOD);: hitung invfact[N] dengan Fermat’s little theorem — fact[N]^(MOD-2) mod MOD = invers fact[N]. Lihat Chapter Modular Inverse .
Baris invfact[i] = (invfact[i+1] * (i+1)) % MOD;: hitung invfact[i] mundur — gunakan relasi invfact[i] = invfact[i+1] * (i+1) mod MOD. O(N).
Lambda C(n, k): C(n, k) = n! / (k! · (n-k)!) = fact[n] · invfact[k] · invfact[n-k] mod MOD. O(1) per query.
Hasil baris pertama C(0,0)=1: hanya satu cara memilih 0 dari 0.
Hasil C(5,2)=10: lima-pilih-dua = 10. Sesuai.

Ringkasan #

Properti modulo: (a ± b) mod m, (a · b) mod m, a^k mod m — selalu modulo setiap operasi.
Pengurangan modulo: tambahkan + m sebelum % m untuk menangani negatif.
Perkalian tiga bilangan modulo wajib di-mod setiap langkah — (a*b*c) mod m = ((a*b mod m) * c) mod m.
Untuk m hingga 2^62, gunakan __int128 untuk perkalian (atau Russian peasant bila tidak portabel).
Aplikasi: binomial coefficient via precompute faktorial + invers — O(N) precompute, O(1) per query.

Properti Dasar Modulo #

Aturan #

Mekanisme: Mengapa Modulo Diperlukan #

Pola Penting: Pengurangan Negatif #

Aturan #

Kode: Pengurangan Modulo yang Aman #

Pola: Perkalian Modular dengan __int128 #

Aturan #

Kode: Perkalian Modular dengan __int128 #

Aplikasi: Binomial Coefficient Modulo #

Aturan #

Kode: Binomial dengan Precompute #

Ringkasan #

Pola: Perkalian Modular dengan `__int128` #