Мотивация и контекст

Почему NTT работает только при определённых модулях? Почему поиск обратного элемента требует простого модуля? Почему полиномы над GF(2) особенные? Ответ на все эти вопросы — в теории алгебраических структур.

В соревновательном программировании алгебраические структуры проявляются постоянно:

• Работа с многочленами над конечными полями (CRC, коды исправления ошибок)
• Умножение матриц над кольцами (задачи на подсчёт путей)
• Быстрые преобразования (NTT требует поля с корнями из единицы нужного порядка)
• Задачи на LFSR (линейные регистры сдвига)
• Дискретный логарифм в группах разного вида

Знание того, что "Z/pZ — поле при простом p", "мультипликативная группа поля циклична", "каждый конечный коммутативный кольцо — произведение локальных колец" — это не академическая роскошь, а практический инструментарий.

---

Теория

Группы

Определение. Группа — это множество G с бинарной операцией ∗, удовлетворяющей:

1. Замкнутость: a ∗ b ∈ G для всех a, b ∈ G
2. Ассоциативность: (a ∗ b) ∗ c = a ∗ (b ∗ c)
3. Нейтральный элемент: существует e ∈ G: e ∗ a = a ∗ e = a
4. Обратный элемент: для каждого a ∈ G существует a⁻¹: a ∗ a⁻¹ = e

Если дополнительно выполняется коммутативность a ∗ b = b ∗ a, группа называется абелевой.

Примеры для CP:

• (Z, +) — целые под сложением: Z — абелева группа
• (Z/nZ, +) — вычеты под сложением: абелева группа порядка n
• (Z/nZ)* = {a : gcd(a,n)=1} — мультипликативная группа вычетов
• GL(n, F_p) — обратимые матрицы над полем: неабелева группа
• Группа точек эллиптической кривой E(F_p): абелева группа

Теорема Лагранжа. Если H — подгруппа конечной группы G, то |H| делит |G|. Следствие: порядок любого элемента делит |G|.

Теорема Кэли-Гамильтона для групп. a^{|G|} = e для любого a ∈ G (для конечных групп). Частный случай: малая теорема Ферма.

Кольца

Определение. Кольцо — это множество R с двумя операциями (+, ·), где:

1. (R, +) — абелева группа
2. Умножение ассоциативно: (a·b)·c = a·(b·c)
3. Дистрибутивность: a·(b+c) = a·b + a·c и (b+c)·a = b·a + c·a

Если умножение коммутативно — коммутативное кольцо. Если есть единица 1 — кольцо с единицей.

Примеры:

• Z, Q, R, C — стандартные числовые кольца
• Z[x] — многочлены с целыми коэффициентами
• Z/nZ — вычеты по модулю n (для любого n, не только простого!)
• M_n(F) — матрицы над полем (некоммутативное кольцо)
• Z[i] — гауссовы целые (см. главу 19)

Область целостности. Коммутативное кольцо с единицей называется областью целостности, если оно не имеет делителей нуля: ab = 0 ⟹ a = 0 или b = 0.

Примеры: Z, Z[x], Z[i]. Контрпример: Z/6Z (2·3 = 6 ≡ 0).

Идеалы

Определение. Подмножество I ⊆ R называется идеалом, если:

1. (I, +) — подгруппа (R, +)
2. Для всех r ∈ R, a ∈ I: r·a ∈ I и a·r ∈ I

Главный идеал. (a) = {r·a : r ∈ R} — идеал, порождённый a.

В Z все идеалы главные: (n) = nZ = {…, −2n, −n, 0, n, 2n, …}.

Факторкольцо R/I. Если I — идеал, то R/I = {a + I : a ∈ R} с операциями (a+I) + (b+I) = (a+b)+I и (a+I)·(b+I) = (ab)+I.

Ключевой пример: Z/nZ = Z/(n) — это именно факторкольцо! Элементы — классы вычетов.

Максимальные идеалы. Идеал m ⊆ R называется максимальным, если m ≠ R и нет идеала между m и R. Теорема: R/m — поле тогда и только тогда, когда m максимальный.

В Z максимальные идеалы — это (p) для простых p. Поэтому Z/(p) = Z/pZ — поле при простом p.

Простые идеалы. p — простой идеал, если R/p — область целостности.

Поля

Определение. Поле — это коммутативное кольцо с единицей, в котором каждый ненулевой элемент обратим. Эквивалентно: F — поле ⟺ единственные идеалы в F — это {0} и F.

Примеры: Q, R, C, Z/pZ (p — простое), GF(p^n) — поле Галуа.

Теорема (Характеристика поля). Характеристика поля F — это наименьшее n > 0 с 1+1+…+1 (n раз) = 0, или 0 если такого нет. Характеристика конечного поля — простое число p.

Теорема (Классификация конечных полей). Для каждого простого p и натурального n существует единственное с точностью до изоморфизма конечное поле GF(p^n) = F_{p^n} порядка p^n. Поля других порядков не существуют.

Конструкция GF(p^n). Возьмём неприводимый многочлен f(x) степени n над GF(p). Тогда:

GF(p^n) ≅ GF(p)[x] / (f(x))

Элементы — многочлены степени < n; операции — по модулю f(x).

Мультипликативная группа конечного поля

Теорема (Гаусс). Мультипликативная группа F* любого конечного поля F является циклической.

Доказательство. Пусть |F*| = n. Для каждого делителя d|n рассмотрим уравнение x^d = 1 в F. Это многочлен степени d, имеющий не более d корней в поле. Число элементов порядка d в любой абелевой группе порядка n равно φ(d) · [число подгрупп порядка d]. Подсчёт показывает, что сумма должна равняться n, что выполняется только при циклической структуре. □

Следствие. Существует примитивный корень g ∈ (Z/pZ)* — элемент порядка p−1. Любой элемент F_p* = {g^0, g^1, ..., g^{p-2}}.

Для CP: это обосновывает существование примитивных корней mod p, используемых в NTT, дискретном логарифме и т.д.

Кольцо Z/nZ

Структура Z/nZ по теореме Китайского остатка (CRT):

Если n = p₁^{a₁} · p₂^{a₂} · ... · p_k^{a_k}, то:

Z/nZ ≅ Z/p₁^{a₁}Z × Z/p₂^{a₂}Z × ... × Z/p_k^{a_k}Z

Это изоморфизм колец! Каждый компонент Z/p_i^{a_i}Z — локальное кольцо с единственным максимальным идеалом (p_i).

Обратимые элементы: (Z/nZ)* ≅ (Z/p₁^{a₁}Z)* × ... — прямое произведение мультипликативных групп. Порядок = φ(n).

Структура (Z/p^kZ)*:

• При p нечётном: (Z/p^kZ)* ≅ Z/φ(p^k)Z = Z/(p-1)p^{k-1}Z — циклическая группа
• При p = 2, k ≥ 3: (Z/2^kZ)* ≅ Z/2 × Z/2^{k-2} — не циклическая

Поля Галуа GF(2^n) в CP

GF(2^n) = GF(2)[x]/(f(x)), где f — неприводимый многочлен степени n над GF(2).

Умножение в GF(2^n): это умножение многочленов по модулю f(x), где коэффициенты берутся mod 2 (т.е. сложение — это XOR).

Применения:

• CRC (Cyclic Redundancy Check): детектирование ошибок
• Коды Рида-Соломона, коды Хэмминга
• Задачи на "xor-независимость" (матроидная теория над GF(2))
• Линейный базис — это базис линейного пространства над GF(2)

Линейный базис (xor-базис). Множество чисел B = {b₁, ..., b_k} образует xor-базис, если каждое число представимо как XOR подмножества B, и ни один b_i не является XOR остальных. Максимальный XOR подмножества массива = максимальный элемент по xor-базису.

---

Ключевые формулы

---

Реализация на C++20

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lll = __int128;

// ==================== Базовые операции в кольцах =============================

ll powmod(ll a, ll b, ll m) {
    ll res = 1; a %= m;
    if (a < 0) a += m;
    while (b > 0) {
        if (b & 1) res = (lll)res * a % m;
        a = (lll)a * a % m;
        b >>= 1;
    }
    return res;
}

ll modinv(ll a, ll m) {
    // Расширенный алгоритм Евклида
    ll g = m, x = 0, y = 1;
    ll ta = a % m;
    if (ta < 0) ta += m;
    ll tr = ta;
    while (tr != 0) {
        ll q = g / tr;
        g -= q * tr; swap(g, tr);
        x -= q * y; swap(x, y);
    }
    if (g != 1) return -1; // обратного не существует
    return (x % m + m) % m;
}

// ==================== Первообразный корень ====================================

// Факторизация φ(p) = p-1
vector<ll> factorize_phi(ll p) {
    ll phi = p - 1;
    vector<ll> primes;
    for (ll q = 2; q * q <= phi; q++) {
        if (phi % q == 0) {
            primes.push_back(q);
            while (phi % q == 0) phi /= q;
        }
    }
    if (phi > 1) primes.push_back(phi);
    return primes;
}

// Найти первообразный корень mod p (p — простое)
ll primitive_root(ll p) {
    ll phi = p - 1;
    auto primes = factorize_phi(p);
    for (ll g = 2; g < p; g++) {
        bool ok = true;
        for (ll q : primes) {
            if (powmod(g, phi / q, p) == 1) { ok = false; break; }
        }
        if (ok) return g;
    }
    return -1; // не найдено (не должно случиться для простых p > 2)
}

// ==================== Дискретный логарифм (Baby-step Giant-step) ================

// Найти x: g^x ≡ a (mod p), 0 ≤ x < p-1
// Алгоритм Шенкса (BSGS) за O(√p)
ll discrete_log(ll g, ll a, ll p) {
    ll m = (ll)ceil(sqrt((double)(p - 1))) + 1;
    // Baby steps: вычислить g^j mod p для j = 0..m-1
    unordered_map<ll, ll> table;
    ll gj = 1;
    for (ll j = 0; j < m; j++) {
        table[gj] = j;
        gj = (lll)gj * g % p;
    }
    // Giant steps: g^{-m}
    ll gm_inv = powmod(powmod(g, m, p), p - 2, p); // g^{-m} mod p
    ll cur = a;
    for (ll i = 0; i <= m; i++) {
        if (table.count(cur)) {
            ll x = i * m + table[cur];
            if (x > 0) return x;
        }
        cur = (lll)cur * gm_inv % p;
    }
    return -1; // решения нет
}

// ==================== Арифметика в GF(2^n) ====================================

// GF(2^32) с примитивным многочленом x^32 + x^7 + x^3 + x^2 + 1
// (используется в CRC-32)
using u32 = unsigned int;

const u32 GF2_32_MOD = 0x100000008D; // x^32 + x^7 + x^3 + x^2 + 1 (неполный - для примера)
// Реальный: 0x04C11DB7 для CRC-32

// Умножение в GF(2^32) без таблицы
u32 gf2_mul(u32 a, u32 b, u32 mod_poly) {
    u32 res = 0;
    while (b > 0) {
        if (b & 1) res ^= a;
        bool high_bit = (a >> 31) & 1;
        a <<= 1;
        if (high_bit) a ^= mod_poly; // редукция по модулю f(x)
        b >>= 1;
    }
    return res;
}

// Возведение в степень в GF(2^n)
u32 gf2_pow(u32 a, u32 b, u32 mod_poly) {
    u32 res = 1;
    while (b > 0) {
        if (b & 1) res = gf2_mul(res, a, mod_poly);
        a = gf2_mul(a, a, mod_poly);
        b >>= 1;
    }
    return res;
}

// ==================== Линейный базис над GF(2) (xor-basis) ====================

struct XorBasis {
    vector<ll> basis;
    // Максимальная размерность
    static const int MAXBIT = 60;

    XorBasis() : basis(MAXBIT + 1, 0) {}

    // Добавить число x в базис
    bool insert(ll x) {
        for (int i = MAXBIT; i >= 0; i--) {
            if (!((x >> i) & 1)) continue;
            if (!basis[i]) {
                basis[i] = x;
                return true; // добавлен новый вектор
            }
            x ^= basis[i];
        }
        return false; // x линейно зависит от базиса
    }

    // Максимальный XOR любого подмножества
    ll max_xor() const {
        ll res = 0;
        for (int i = MAXBIT; i >= 0; i--)
            res = max(res, res ^ basis[i]);
        return res;
    }

    // Максимальный XOR элементов множества с числом val
    ll max_xor_with(ll val) const {
        ll res = val;
        for (int i = MAXBIT; i >= 0; i--)
            res = max(res, res ^ basis[i]);
        return res;
    }

    // Проверка, достижимо ли число x как XOR подмножества
    bool can_make(ll x) const {
        for (int i = MAXBIT; i >= 0; i--) {
            if (!((x >> i) & 1)) continue;
            if (!basis[i]) return false;
            x ^= basis[i];
        }
        return true; // x == 0 после редукции
    }

    // k-е наименьшее число, достижимое XOR подмножества (0-индексация)
    // Требует "приведения" базиса к ступенчатому виду
    ll kth_xor(ll k) const {
        // Строим приведённый базис
        vector<ll> b;
        for (int i = MAXBIT; i >= 0; i--)
            if (basis[i]) b.push_back(basis[i]);
        // Приводим к ступенчатому виду (Гаусс)
        vector<ll> reduced = b;
        for (int i = 0; i < (int)reduced.size(); i++) {
            for (int j = 0; j < i; j++) {
                reduced[j] = min(reduced[j], reduced[j] ^ reduced[i]);
            }
        }
        reverse(reduced.begin(), reduced.end());
        ll res = 0;
        for (int i = 0; i < (int)reduced.size(); i++) {
            if ((k >> i) & 1) res ^= reduced[i];
        }
        return res;
    }
};

// ==================== Китайская теорема об остатках (обобщённая) ===============

// Найти x: x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂)
// Возвращает {x, lcm(m₁, m₂)} или {-1, -1} если нет решения
pair<ll,ll> crt(ll a1, ll m1, ll a2, ll m2) {
    ll g = __gcd(m1, m2);
    if ((a2 - a1) % g != 0) return {-1, -1};
    ll lcm = m1 / g * m2;
    ll diff = (a2 - a1) / g;
    ll m1g = m1 / g;
    ll inv = modinv(m1g % (m2/g), m2/g);
    ll x = (a1 + m1 * (diff % (m2/g) * inv % (m2/g))) % lcm;
    return {(x + lcm) % lcm, lcm};
}

// CRT для набора сравнений
ll crt_multiple(vector<pair<ll,ll>>& congruences) {
    ll x = congruences[0].first;
    ll m = congruences[0].second;
    for (int i = 1; i < (int)congruences.size(); i++) {
        auto [xi, mi] = congruences[i];
        auto [new_x, new_m] = crt(x, m, xi, mi);
        if (new_x == -1) return -1;
        x = new_x;
        m = new_m;
    }
    return x;
}

// ==================== Неприводимые многочлены над GF(p) ====================

// Проверка неприводимости многочлена f(x) над GF(p)
// Многочлен задаётся как вектор коэффициентов (от старшего)
// (упрощённая версия для GF(2))

bool is_irreducible_gf2(u32 poly, int deg) {
    // Алгоритм Бен-Ора: f неприводим ⟺
    // для всех k = 1..deg/2: gcd(f, x^{2^k} - x) = 1 в GF(2)[x]
    // Вычисляем x^{2^k} mod f итерационно
    u32 x_pow = 2; // x^1
    for (int k = 1; 2*k <= deg; k++) {
        // Возводим в квадрат deg раз: x^{2^k} mod f
        u32 xk = gf2_pow(x_pow, (u32)1 << k, poly);
        u32 diff = xk ^ 2; // x^{2^k} - x = x^{2^k} XOR x (в GF(2))
        // gcd(f, diff) в GF(2)[x] через алгоритм Евклида
        // (реализация опущена для краткости)
        if (diff == 0) return false;
    }
    return true;
}

int main() {
    // Первообразный корень mod 998244353
    ll p = 998244353; // = 119 * 2^23 + 1
    cout << "Primitive root mod " << p << ": " << primitive_root(p) << "\n"; // 3

    // Дискретный логарифм: 3^x ≡ 7 (mod 13)
    ll g = 3, a = 7, mod = 13;
    ll x = discrete_log(g, a, mod);
    cout << "3^" << x << " ≡ 7 (mod 13): " << powmod(g, x, mod) << "\n";

    // XorBasis
    XorBasis xb;
    for (ll v : {1LL, 2LL, 3LL, 4LL, 5LL}) xb.insert(v);
    cout << "Max XOR from {1,2,3,4,5} = " << xb.max_xor() << "\n"; // 7

    // CRT: x ≡ 3 (mod 5), x ≡ 4 (mod 7) → x ≡ 18 (mod 35)
    auto [res, mod_res] = crt(3, 5, 4, 7);
    cout << "CRT: x = " << res << " (mod " << mod_res << ")\n"; // 18 mod 35

    return 0;
}

Анализ сложности.

• primitive_root(p): O(p^{1/2} log p) — факторизация + O(log p / log log p) попыток в среднем.
• discrete_log (BSGS): O(√p · log p) — время и O(√p) памяти.
• XorBasis::insert: O(60) = O(log(max_val)).
• crt: O(log(m₁ + m₂)) — расширенный Евклид.

---

Разбор задачи 1 (средняя)

Задача. Дан массив из n ≤ 10^5 чисел a_i ≤ 10^18. Найти максимальный XOR любого непустого подмножества.

Решение. Классическое применение линейного xor-базиса.

XorBasis xb;
for (ll a : arr) xb.insert(a);
cout << xb.max_xor() << "\n";

Почему это работает? XOR любого подмножества — это линейная комбинация (над GF(2)) исходных элементов. Линейный базис — это базис соответствующего подпространства GF(2)^{60}. Максимальный XOR — максимум по этому подпространству, который жадно находится проходом по базису от старшего бита к младшему.

Сложность: O(n · 60) = O(n log(max_val)).

---

Разбор задачи 2 (сложная)

Задача. Дан массив из n ≤ 3·10^5 чисел. Найти k-й наименьший XOR подмножества (0 — пустое, дающее 0).

Решение. Строим xor-базис, приводим его к "ступенчатому" виду (reduce), где каждый вектор базиса имеет ровно один "старший" бит и не влияет на более старшие биты других векторов. После приведения k-й элемент читается как двоичная запись k: i-й бит k определяет, используется ли i-й вектор базиса.

// Приведение базиса к ступенчатому виду
void reduce_basis(XorBasis& xb) {
    for (int i = 60; i >= 0; i--) {
        if (!xb.basis[i]) continue;
        for (int j = i+1; j <= 60; j++) {
            if ((xb.basis[j] >> i) & 1)
                xb.basis[j] ^= xb.basis[i];
        }
    }
}
// После этого kth_xor(k) даёт k-й элемент

Сложность: O(n · 60 + 60²) — вставка + редукция.

---

Разбор задачи 3 (ICPC WF / CF Div.1 E)

Задача (CF 1336F, адаптация). Дан граф на n вершинах. Каждому ребру (u, v) назначен вес w(u,v). Найти простой путь с максимальным XOR весов рёбер.

Решение (линейный базис на DFS-дереве).

Ключевая теорема. Пространство XOR всех простых путей между двумя вершинами s и t в графе — это линейное аффинное подпространство над GF(2). Базис этого пространства — это XOR фундаментальных циклов в любом остовном дереве.

Алгоритм:

1. Построить остовное дерево (DFS).
2. Для каждого нетревого ребра (back edge) вычислить XOR цикла — XOR весов рёбер цикла в дереве.
3. Добавить все такие XOR в линейный базис.
4. Максимальный XOR пути s → t = xb.max_xor_with(path_xor(s, t)), где path_xor — XOR весов рёбер в дереве от s до t.

// Нахождение XOR пути в дереве (LCA + XOR по глубине)
vector<ll> depth_xor; // depth_xor[v] = XOR весов от корня до v

ll path_xor_tree(int u, int v) {
    return depth_xor[u] ^ depth_xor[v]; // при LCA = lca(u,v), XOR = d[u]^d[v]
    // (точнее: XOR пути u→lca→v = depth_xor[u] ^ depth_xor[v])
}

void solve() {
    // DFS для построения depth_xor
    // ...
    XorBasis xb;
    // Добавить XOR циклов
    for (auto [u, v, w] : back_edges) {
        xb.insert(path_xor_tree(u, v) ^ w);
    }
    // Ответ: максимум path_xor_tree(s, t) ^ (XOR некоторого подмножества циклов)
    // = xb.max_xor_with(path_xor_tree(s, t))
}

Почему XOR пути = XOR из дерева? Любой другой путь получается из пути в дереве XOR-ом с набором фундаментальных циклов. Поэтому множество всех достижимых XOR путей = аффинное подпространство {d(s,t) XOR span(циклы)}.

---

Задачи для самостоятельного решения

---

Типичные ошибки

1. Путаница между Z/pZ и GF(p^n). Z/pZ — это поле GF(p), но GF(p^n) при n > 1 — это поле многочленов, не Z/p^nZ! Z/p^nZ при n > 1 — не поле, так как pZ/p^nZ — нетривиальный максимальный идеал, но в Z/p^nZ есть делители нуля (например, p · p^{n-1} = p^n ≡ 0).
2. Неправильный XOR-базис при удалении элементов. Стандартный xor-базис не поддерживает удаление. Для удаления используют технику "онлайн базиса" или сегментное дерево.
3. BSGS для нециклических групп. Классический BSGS работает только если g — генератор группы. Для поиска x : g^x ≡ a нужно сначала определить порядок g.
4. Забыть про характеристику при работе с GF(p). В GF(2) сложение = XOR, а "−1 = 1". Это ломает алгоритмы, написанные для char ≠ 2.
5. CRT с нет решения. При gcd(m₁, m₂) ∤ (a₂ − a₁) система не имеет решения — нужно обрабатывать этот случай явно.

---

Совет профессионала

Линейный xor-базис — один из наиболее универсальных инструментов в CP. Запомните три ключевых паттерна использования:

1. Максимальный XOR подмножества: добавить все элементы в базис, жадно взять максимум.
2. XOR пути в графе: DFS + фундаментальные циклы в базис + аффинный сдвиг.
3. Линейная независимость: can_make(x) == true ⟺ x в span базиса.

Для задач, где нужен n-й XOR по порядку, обязательно редуцируйте базис (remove high bits from lower vectors). После редукции базис соответствует двоичному счётчику.

Ещё один полезный факт: ранг матрицы над GF(2) — это размер xor-базиса строк (или столбцов). Это открывает путь к задачам на линейную алгебру над GF(2) через xor-базис.

---

Итог

Алгебраические структуры — группы, кольца, поля — дают единый язык для описания задач с арифметикой. Ключевые результаты для CP: Z/pZ — поле при простом p; мультипликативная группа конечного поля циклична; GF(p^n) единственно и строится как кольцо вычетов многочленов; CRT разбивает Z/nZ на произведение локальных колец. Линейный xor-базис — это линейная алгебра над GF(2) в конкретном алгоритмическом обличии, одном из самых полезных инструментов соревнований.