Αριθμητική modulo και συνδυαστική
Γρήγορη ύψωση σε δύναμη, αντίστροφος με το μικρό θεώρημα του Fermat, και σε μετά από προεπεξεργασία .
Πότε
«Τύπωσε την απάντηση modulo ». Σχεδόν κάθε πρόβλημα μέτρησης.
Η ιδέα
Ύψωση σε δύναμη. με πολλαπλασιασμούς: γράφεις το στο δυαδικό, τετραγωνίζεις το σε κάθε bit, και πολλαπλασιάζεις στο αποτέλεσμα όσα αντιστοιχούν σε bit 1.
Αντίστροφος. Για πρώτο και , το μικρό θεώρημα του Fermat δίνει , άρα
Ισχύει μόνο για πρώτο modulus. Για άλλο modulus χρειάζεται ο επεκτεταμένος Ευκλείδης, και ο αντίστροφος υπάρχει μόνο αν .
Διωνυμικοί συντελεστές. Προϋπολογίζεις για , και με μία ύψωση. Μετά πας προς τα πίσω: . Έτσι
σε , με προεπεξεργασία και μία μόνο ύψωση σε δύναμη.
Η κίνηση που ξεκλειδώνει προβλήματα
Exponentiation II ζητά . Το είναι τεράστιο, αλλά από τον Fermat ο εκθέτης μετράει μόνο modulo : υπολόγισε και μετά . (Προσοχή όταν .)
Distributing Apples: ίδια μήλα σε παιδιά είναι (αστέρια και ράβδοι).
Παγίδες
- Κάθε γινόμενο δύο αριθμών χωράει σε
long long(, ενώ το όριο είναι ). Τρία όχι: πάρε modulo μετά από κάθε πολλαπλασιασμό. - Η αφαίρεση δίνει αρνητικό:
(a - b + MOD) % MOD. - Το
binpowεδώ δέχεται και αρνητικό , και modulus 1 (όπου όλα είναι 0). Το test ελέγχει και τα δύο.
Κώδικας
Χωρίς main: μπαίνει κάτω από τα #include, το using namespace std και το using ll = long long.
// 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
Με τη σειρά: το πρώτο είναι η καθαρή εφαρμογή, τα επόμενα θέλουν μια παραλλαγή.
- Exponentiation · Mathematics
- Exponentiation II · Mathematics
- Binomial Coefficients · Mathematics
- Creating Strings II · Mathematics
- Distributing Apples · Mathematics
Περισσότερα στο USACO Guide
- Modular Arithmetic · usaco.guide/gold/modular
- Combinatorics · usaco.guide/gold/combo
Στα αγγλικά, με επιπλέον προβλήματα ανά επίπεδο.