📈 Полиноми и Пълна реализация на Дълги числа (BigInt)

🧮 Дълги числа (BigInt) - Детайлна реализация

Стандартните типове данни (long long) са ограничени до \(\approx 9 \cdot 10^{18}\). В задачи с по-големи числа (напр. 100-цифрени) трябва да имплементираме собствена структура.

Избор на база

Вместо да пазим по една цифра (база 10), е много по-ефективно да пазим по 9 цифри (база \(10^9\)) в един int. Това намалява паметта и броя операции 9 пъти. - База \(10^9\) се побира в int, а произведението на две "цифри" (\(10^{18}\)) се побира в long long.

Пълна структура BigInt

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>

using namespace std;

const int BASE = 1e9;

struct BigInt {
    vector<int> digits;

    BigInt() {}
    BigInt(long long v) {
        if (v == 0) digits.push_back(0);
        while (v > 0) {
            digits.push_back(v % BASE);
            v /= BASE;
        }
    }
    BigInt(string s) {
        for (int i = (int)s.length(); i > 0; i -= 9) {
            if (i < 9)
                digits.push_back(stoi(s.substr(0, i)));
            else
                digits.push_back(stoi(s.substr(i - 9, 9)));
        }
        trim();
    }

    void trim() {
        while (digits.size() > 1 && digits.back() == 0) {
            digits.pop_back();
        }
    }

    // Оператор за извеждане
    friend ostream& operator<<(ostream& os, const BigInt& bi) {
        if (bi.digits.empty()) { os << 0; return os; }
        os << bi.digits.back();
        for (int i = (int)bi.digits.size() - 2; i >= 0; i--) {
            os << setfill('0') << setw(9) << bi.digits[i];
        }
        return os;
    }

    // Сравнение
    bool operator<(const BigInt& other) const {
        if (digits.size() != other.digits.size())
            return digits.size() < other.digits.size();
        for (int i = (int)digits.size() - 1; i >= 0; i--)
            if (digits[i] != other.digits[i])
                return digits[i] < other.digits[i];
        return false;
    }

    // Събиране
    BigInt operator+(const BigInt& other) const {
        BigInt res;
        int carry = 0;
        for (size_t i = 0; i < max(digits.size(), other.digits.size()) || carry; ++i) {
            int current = carry + (i < digits.size() ? digits[i] : 0) + 
                          (i < other.digits.size() ? other.digits[i] : 0);
            res.digits.push_back(current % BASE);
            carry = current / BASE;
        }
        return res;
    }

    // Изваждане (приемаме, че *this >= other)
    BigInt operator-(const BigInt& other) const {
        BigInt res;
        int carry = 0;
        for (size_t i = 0; i < digits.size(); ++i) {
            int current = digits[i] - carry - (i < other.digits.size() ? other.digits[i] : 0);
            if (current < 0) {
                current += BASE;
                carry = 1;
            } else {
                carry = 0;
            }
            res.digits.push_back(current);
        }
        res.trim();
        return res;
    }

    // Умножение с късо число (long long)
    BigInt operator*(long long v) const {
        BigInt res;
        long long carry = 0;
        for (int d : digits) {
            long long cur = d * v + carry;
            res.digits.push_back(cur % BASE);
            carry = cur / BASE;
        }
        while (carry) {
            res.digits.push_back(carry % BASE);
            carry /= BASE;
        }
        res.trim();
        return res;
    }

    // Умножение на две BigInt числа
    BigInt operator*(const BigInt& other) const {
        BigInt res;
        res.digits.resize(digits.size() + other.digits.size(), 0);
        for (size_t i = 0; i < digits.size(); ++i) {
            long long carry = 0;
            for (size_t j = 0; j < other.digits.size() || carry; ++j) {
                long long cur = res.digits[i + j] + digits[i] * 1LL * (j < other.digits.size() ? other.digits[j] : 0) + carry;
                res.digits[i + j] = cur % BASE;
                carry = cur / BASE;
            }
        }
        res.trim();
        return res;
    }
};

---

📈 Полиноми

Полиномите са обобщение на числата. Ако число е полином, оценен в точка \(x=10\) (за десетична система), то операциите са аналогични.

Схема на Хорнер - Оптимизация

Схемата на Хорнер намалява броя на умноженията при пресмятане на \(P(x)\). Вместо \(a_n x^n + \dots + a_0\), записваме: $\((\dots((a_n x + a_{n-1})x + a_{n-2})x + \dots)x + a_0\)$ Така са нужни само \(N\) умножения и \(N\) събирания.

Умножение на полиноми

1. Наивен метод: \(O(N^2)\) - идентичен с умножението на BigInt по-горе.
2. Бързо умножение (FFT): \(O(N \log N)\). Преобразува полиномите в стойности (Point-Value form), умножава ги линейно и ги връща обратно. (Виж Тема 44).

Интерполация на Лагранж

Ако имаме \(N+1\) точки \((x_i, y_i)\), съществува единствен полином от степен \(\le N\), който минава през тях. $\(P(x) = \sum_{j=0}^{N} y_j L_j(x), \quad \text{където } L_j(x) = \prod_{i \neq j} \frac{x - x_i}{x_j - x_i}\)$

Това е полезно за възстановяване на функция по нейните стойности, особено в задачи за намиране на "следващия член на редицата".

---

🏁 Заключение

Имплементацията на BigInt е често срещана подзадача. Добре е да имате подготвен и тестван шаблон ("черна кутия"), който да копирате по време на състезание. Внимавайте с "trim" функцията за премахване на водещите нули, тъй като те могат да счупят логиката на сравнението или извеждането.

---

11. Работа с полиноми - практически примери

11.1. Оценяване на полином с Хорнер

// P(x) = a[0] + a[1]*x + a[2]*x^2 + ... + a[n]*x^n
double horner(vector<double>& a, double x) {
    double result = 0;
    for (int i = a.size() - 1; i >= 0; i--) {
        result = result * x + a[i];
    }
    return result;
}

11.2. Събиране на полиноми

vector<int> addPolynomials(vector<int>& p1, vector<int>& p2) {
    int maxDegree = max(p1.size(), p2.size());
    vector<int> result(maxDegree, 0);

    for (int i = 0; i < p1.size(); i++) result[i] += p1[i];
    for (int i = 0; i < p2.size(); i++) result[i] += p2[i];

    return result;
}

11.3. Умножение на полиноми (наивен метод)

vector<int> multiplyPolynomials(vector<int>& p1, vector<int>& p2) {
    vector<int> result(p1.size() + p2.size() - 1, 0);

    for (int i = 0; i < p1.size(); i++) {
        for (int j = 0; j < p2.size(); j++) {
            result[i + j] += p1[i] * p2[j];
        }
    }

    return result;
}

Сложност: \(O(N \times M)\), където \(N\) и \(M\) са степените на полиномите.

---

12. Интерполация - практическо приложение

Задача: Намиране на следващ член в редица

Дадени са първите \(N+1\) членове на редица. Намерете \((N+2)\)-рия член.

Решение: Ако редицата се описва от полином от степен \(\le N\), можем да използваме интерполация на Лагранж.

// Дадени точки (0, y0), (1, y1), ..., (n, yn)
// Намираме стойността на полинома в точка x
double lagrangeInterpolation(vector<double>& y, double x) {
    int n = y.size();
    double result = 0;

    for (int j = 0; j < n; j++) {
        double term = y[j];
        for (int i = 0; i < n; i++) {
            if (i != j) {
                term *= (x - i) / (j - i);
            }
        }
        result += term;
    }

    return result;
}

Пример: Ако имаме \(y = [1, 4, 9, 16, 25]\) (квадратите на числата), това е полином от степен 2. Можем да намерим следващия член за \(x=5\): \(P(5) = 36\).

---

13. Връзка с динамичното програмиране

Полиномите често се появяват в DP задачи, особено при: * Generating functions (производящи функции). * Комбинаторика (биномиални коефициенти, Catalan числа).

Например, броят на начините да разменим монети може да се представи като коефициенти в произведение на полиноми.

---

14. Задачи за упражнение

1. Project Euler 101: Optimum Polynomial (интерполация).
2. Codeforces 528D: Fuzzy Search (може да се реши с FFT умножение на полиноми).
3. SPOJ POLYMUL: Директно умножение на полиноми.
4. UVa 10105: Polynomial Coefficients (комбинаторика с полиноми).

---

🏁 Финални съвети

• За BigInt задачи винаги тествайте с екстремни случаи (0, много големи числа, еднакви числа).
• При полиноми внимавайте с overflow - използвайте long long или модулна аритметика.
• Схемата на Хорнер е елегантна и ефективна - използвайте я винаги, когато оценявате полином.
• За конкурси с позволени външни библиотеки (GMP, NTL) научете се да ги използвате - спестяват време.

Владеенето на работата с произволно големи числа и полиноми отваря вратата към много напреднали алгоритми като FFT, NTT и различни криптографски приложения!