uniolympiads English

Αριθμητική modulo και συνδυαστική

Γρήγορη ύψωση σε δύναμη, αντίστροφος με το μικρό θεώρημα του Fermat, και (nr)\binom{n}{r} σε O(1)O(1) μετά από προεπεξεργασία O(n)O(n).

Πότε

«Τύπωσε την απάντηση modulo 109+710^9 + 7». Σχεδόν κάθε πρόβλημα μέτρησης.

Η ιδέα

Ύψωση σε δύναμη. aea^e με O(log⁡e)O(\log e) πολλαπλασιασμούς: γράφεις το ee στο δυαδικό, τετραγωνίζεις το aa σε κάθε bit, και πολλαπλασιάζεις στο αποτέλεσμα όσα αντιστοιχούν σε bit 1.

Αντίστροφος. Για πρώτο pp και a≢0a \not\equiv 0, το μικρό θεώρημα του Fermat δίνει ap−1≡1a^{p-1} \equiv 1, άρα

a−1≡ap−2(modp).a^{-1} \equiv a^{p-2} \pmod p .

Ισχύει μόνο για πρώτο modulus. Για άλλο modulus χρειάζεται ο επεκτεταμένος Ευκλείδης, και ο αντίστροφος υπάρχει μόνο αν gcd⁡(a,m)=1\gcd(a, m) = 1.

Διωνυμικοί συντελεστές. Προϋπολογίζεις n!n! για n≤Nn \le N, και (N!)−1(N!)^{-1} με μία ύψωση. Μετά πας προς τα πίσω: ((i−1)!)−1=(i!)−1⋅i((i-1)!)^{-1} = (i!)^{-1} \cdot i. Έτσι

(nr)=n!⋅(r!)−1⋅((n−r)!)−1\binom{n}{r} = n! \cdot (r!)^{-1} \cdot ((n-r)!)^{-1}

σε O(1)O(1), με O(N)O(N) προεπεξεργασία και μία μόνο ύψωση σε δύναμη.

Η κίνηση που ξεκλειδώνει προβλήματα

Exponentiation II ζητά abc mod pa^{b^c} \bmod p. Το bcb^c είναι τεράστιο, αλλά από τον Fermat ο εκθέτης μετράει μόνο modulo p−1p - 1: υπολόγισε e=bc mod (p−1)e = b^c \bmod (p-1) και μετά ae mod pa^e \bmod p. (Προσοχή όταν a≡0a \equiv 0.)

Distributing Apples: mm ίδια μήλα σε nn παιδιά είναι (n+m−1m)\binom{n + m - 1}{m} (αστέρια και ράβδοι).

Παγίδες

  • Κάθε γινόμενο δύο αριθμών <109+7< 10^9 + 7 χωράει σε long long (<1.01⋅1018< 1.01 \cdot 10^{18}, ενώ το όριο είναι 9.2⋅10189.2 \cdot 10^{18}). Τρία όχι: πάρε modulo μετά από κάθε πολλαπλασιασμό.
  • Η αφαίρεση δίνει αρνητικό: (a - b + MOD) % MOD.
  • Το binpow εδώ δέχεται και αρνητικό aa, και modulus 1 (όπου όλα είναι 0). Το test ελέγχει και τα δύο.

Κώδικας

Χωρίς main: μπαίνει κάτω από τα #include, το using namespace std και το using ll = long long.

cpp/modular.cpp
// Modular arithmetic for a prime modulus: fast power, inverse (Fermat), binomial coefficients.
// binpow is O(log e); after initFactorials(N), nCr is O(1) for n <= N.

const ll MOD = 1000000007;

ll binpow(ll a, ll e, ll mod = MOD) {
    a %= mod;
    if (a < 0) {
        a += mod;
    }
    ll result = 1 % mod;
    while (e > 0) {
        if (e & 1) {
            result = result * a % mod;
        }
        a = a * a % mod;
        e >>= 1;
    }
    return result;
}

// a^(p-2) is the inverse of a modulo a prime p, for a not divisible by p.
ll inverse(ll a, ll mod = MOD) {
    return binpow(a, mod - 2, mod);
}

vector<ll> fact;
vector<ll> invFact;

void initFactorials(int maxN) {
    fact.assign(maxN + 1, 1);
    invFact.assign(maxN + 1, 1);
    for (int i = 1; i <= maxN; i++) {
        fact[i] = fact[i - 1] * i % MOD;
    }
    invFact[maxN] = inverse(fact[maxN]);
    for (int i = maxN; i >= 1; i--) {
        invFact[i - 1] = invFact[i] * i % MOD;
    }
}

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

Ελέγχθηκε σε 20.000 τυχαίες περιπτώσεις απέναντι σε αργή, προφανώς σωστή λύση, με AddressSanitizer και UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).

Για εξάσκηση στο CSES

Με τη σειρά: το πρώτο είναι η καθαρή εφαρμογή, τα επόμενα θέλουν μια παραλλαγή.

Περισσότερα στο USACO Guide

Στα αγγλικά, με επιπλέον προβλήματα ανά επίπεδο.