Хоёртын зэрэгт дэвшүүлэлт¶

Хоёртын зэрэгт дэвшүүлэлт (квадратаар зэрэгт дэвшүүлэх гэж бас нэрлэдэг) нь $a^n$ утгыг, энд $n$ нь сөрөг биш бүхэл тоо, зөвхөн $O(\log n)$ удаагийн үржүүлэлтээр тооцоолох боломж олгодог арга юм (энгийн аргаар бол $O(n)$ удаагийн үржүүлэлт шаардагдана).

Мөн энэ нь associativity бүхий аливаа үйлдэлд хэрэглэгдэх боломжтой тул арифметиктэй хамааралгүй олон бодлогод чухал хэрэглээтэй:

$$(X \cdot Y) \cdot Z = X \cdot (Y \cdot Z)$$

Хамгийн тодорхой жишээ нь модулиар үржүүлэх, матриц үржүүлэх, түүнчлэн доор авч үзэх бусад бодлогууд юм.

Алгоритм¶

$a$-г $n$ зэрэгт дэвшүүлэхийг энгийнээр $a$-г $n - 1$ удаа үржүүлэх байдлаар илэрхийлнэ: $a^{n} = a \cdot a \cdot \ldots \cdot a$. Гэвч $a$ эсвэл $n$ том байх үед энэ арга практикт тохиромжгүй.

$a^{b+c} = a^b \cdot a^c$ ба $a^{2b} = a^b \cdot a^b = (a^b)^2$.

Хоёртын зэрэгт дэвшүүлэлтийн санаа нь зэрэг илтгэгчийн хоёртын дүрслэлийг ашиглан ажлыг хуваах явдал юм.

$n$-г хоёртын системд бичье, жишээ нь:

$$3^{13} = 3^{1101_2} = 3^8 \cdot 3^4 \cdot 3^1$$

$n$ тоо хоёртын системд яг $\lfloor \log_2 n \rfloor + 1$ оронтой байдаг тул, хэрэв бид $a^1, a^2, a^4, a^8, \dots, a^{2^{\lfloor \log_2 n \rfloor}}$ зэргүүдийг мэдэж байвал зөвхөн $O(\log n)$ удаагийн үржүүлэлт хийхэд хангалттай.

Тэгэхээр бид эдгээрийг хурдан тооцоолох аргыг мэдэхэд л хангалттай. Аз болоход энэ нь маш хялбар, учир нь дараалал дахь элемент бүр өмнөх элементийнхээ квадрат байдаг.

$$\begin{align} 3^1 &= 3 \\ 3^2 &= \left(3^1\right)^2 = 3^2 = 9 \\ 3^4 &= \left(3^2\right)^2 = 9^2 = 81 \\ 3^8 &= \left(3^4\right)^2 = 81^2 = 6561 \end{align}$$

Тэгэхээр $3^{13}$-ийн эцсийн хариуг гаргахын тулд бид зөвхөн гурвыг нь үржүүлэхэд хангалттай ($n$-ийн харгалзах бит тавигдаагүй тул $3^2$-ыг алгасна): $3^{13} = 6561 \cdot 81 \cdot 3 = 1594323$

Энэ алгоритмын эцсийн complexity нь $O(\log n)$: бид $a$-гийн $\log n$ зэргийг тооцоолж, дараа нь эцсийн хариуг гаргахын тулд хамгийн ихдээ $\log n$ удаа үржүүлэх хэрэгтэй.

Дараах рекурсив арга нь ижил санааг илэрхийлнэ:

$$a^n = \begin{cases} 1 &\text{хэрэв } n == 0 \\ \left(a^{\frac{n}{2}}\right)^2 &\text{хэрэв } n > 0 \text{ ба } n \text{ тэгш}\\ \left(a^{\frac{n - 1}{2}}\right)^2 \cdot a &\text{хэрэв } n > 0 \text{ ба } n \text{ сондгой}\\ \end{cases}$$

Implementation¶

First the recursive approach, which is a direct translation of the recursive formula:

long long binpow(long long a, long long b) {
    if (b == 0)
        return 1;
    long long res = binpow(a, b / 2);
    if (b % 2)
        return res * res * a;
    else
        return res * res;
}

The second approach accomplishes the same task without recursion. It computes all the powers in a loop, and multiplies the ones with the corresponding set bit in $n$. Although the complexity of both approaches is identical, this approach will be faster in practice since we don't have the overhead of the recursive calls.

long long binpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

Хэрэглээ¶

Тоог модулиар том зэрэгт дэвшүүлэх үр ашигтай тооцоолол¶

Бодлого: $x^n \bmod m$-г тооцоол. Энэ бол маш түгээмэл үйлдэл. Жишээ нь модулийн үржүүлэлтийн урвуу элементийг олоход ашиглагддаг.

Шийдэл: Модулийн үйлдэл үржүүлэлтэд саад болохгүйг ($a \cdot b \equiv (a \bmod m) \cdot (b \bmod m) \pmod m$) бид мэдэх тул ижил кодыг шууд ашиглаж, үржүүлэлт бүрийг модулиар үржүүлэлтээр солиход хангалттай:

long long binpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

Тэмдэглэл: $b >> m$ байх үед энэ алгоритмыг хурдасгах боломжтой. Хэрэв $m$ эерэг тоо ба $\gcd(x, m) = 1$ бол, анхны $m$-ийн хувьд $x^n \equiv x^{n \bmod (m-1)} \pmod{m}$, нийлмэл $m$-ийн хувьд $x^n \equiv x^{n \bmod{\phi(m)}} \pmod{m}$ болно. Энэ нь Фермагийн бага теорем ба Эйлерийн теоремоос шууд гарна, дэлгэрэнгүйг Модулийн урвуу өгүүллээс үзнэ үү.

Фибоначчийн тоог үр ашигтай тооцоолох¶

Бодлого: $n$ дугаар Фибоначчийн тоо $F_n$-г тооцоол.

Шийдэл: Дэлгэрэнгүйг Фибоначчийн тоо өгүүллээс үзнэ үү. Энд бид зөвхөн алгоритмын товч тоймыг авч үзнэ. Дараагийн Фибоначчийн тоог олоход өмнөх хоёр тоо л хэрэгтэй, учир нь $F_n = F_{n-1} + F_{n-2}$. Бид энэ хувиргалтыг тодорхойлох $2 \times 2$ матриц байгуулж болно: $F_i$ ба $F_{i+1}$-ээс $F_{i+1}$ ба $F_{i+2}$ рүү шилжих шилжилт. Жишээ нь, энэ хувиргалтыг $F_0$ ба $F_1$ хос дээр хэрэглэвэл $F_1$ ба $F_2$ болж өөрчлөгдөнө. Тиймээс бид энэ хувиргалтын матрицыг $n$ зэрэгт дэвшүүлснээр $F_n$-г $O(\log n)$ хугацаанд олох боломжтой.

Сэлгэмэлийг $k$ удаа хэрэглэх¶

Бодлого: Танд $n$ урттай дараалал өгөгдсөн. Түүн дээр өгөгдсөн сэлгэмэлийг $k$ удаа хэрэглэ.

Шийдэл: Хоёртын зэрэгт дэвшүүлэлт ашиглан сэлгэмэлийг $k$ зэрэгт дэвшүүлээд, дараа нь түүнийг дараалал дээр хэрэглэ. Ингэснээр $O(n \log k)$ time complexity-тэй болно.

vector<int> applyPermutation(vector<int> sequence, vector<int> permutation) {
    vector<int> newSequence(sequence.size());
    for(int i = 0; i < sequence.size(); i++) {
        newSequence[i] = sequence[permutation[i]];
    }
    return newSequence;
}

vector<int> permute(vector<int> sequence, vector<int> permutation, long long k) {
    while (k > 0) {
        if (k & 1) {
            sequence = applyPermutation(sequence, permutation);
        }
        permutation = applyPermutation(permutation, permutation);
        k >>= 1;
    }
    return sequence;
}

Тэмдэглэл: Энэ бодлогыг сэлгэмэлийн граф байгуулж, цикл бүрийг тусад нь авч үзэх замаар шугаман хугацаанд илүү үр ашигтай бодох боломжтой. Дараа нь та $k$-г циклийн хэмжээгээр модулиар авч, тухайн циклд багтах тоо бүрийн эцсийн байрлалыг олж болно.

Цэгүүдийн олонлогт геометрийн үйлдлүүдийн олонлогийг хурдан хэрэглэх¶

Бодлого: $n$ ширхэг $p_i$ цэг өгөгдсөн, цэг бүр дээр $m$ хувиргалт хэрэглэ. Хувиргалт бүр нь шилжүүлэлт, масштаблалт, эсвэл өгөгдсөн тэнхлэгийг тойрсон өгөгдсөн өнцгөөр эргүүлэлт байж болно. Мөн өгөгдсөн хувиргалтуудын жагсаалтыг $k$ удаа хэрэглэдэг "давталт" үйлдэл байдаг ("давталт" үйлдлүүд нь үүрлэсэн байж болно). Та бүх хувиргалтыг $O(n \cdot length)$-аас хурдан хэрэглэх ёстой, энд $length$ нь хэрэглэгдэх хувиргалтуудын нийт тоо ("давталт" үйлдлүүдийг задалсны дараах).

Шийдэл: Өөр өөр төрлийн хувиргалтууд координатыг хэрхэн өөрчилдгийг харцгаая:

Шилжүүлэх үйлдэл: координат бүр дээр өөр өөр тогтмолыг нэмнэ.
Масштаблах үйлдэл: координат бүрийг өөр өөр тогтмолоор үржүүлнэ.
Эргүүлэх үйлдэл: хувиргалт нь илүү нарийн төвөгтэй (энд дэлгэрэнгүй авч үзэхгүй), гэхдээ шинэ координат бүрийг хуучин координатуудын шугаман комбинац хэлбэрээр илэрхийлж болно.

Таны харж байгаагаар хувиргалт бүрийг координат дээрх шугаман үйлдэл хэлбэрээр илэрхийлж болно. Тиймээс хувиргалтыг дараах хэлбэрийн $4 \times 4$ матрицаар бичиж болно:

$$\begin{pmatrix} a_{11} & a_ {12} & a_ {13} & a_ {14} \\ a_{21} & a_ {22} & a_ {23} & a_ {24} \\ a_{31} & a_ {32} & a_ {33} & a_ {34} \\ a_{41} & a_ {42} & a_ {43} & a_ {44} \end{pmatrix}$$

Энэ матрицыг хуучин координатууд ба нэгжээс бүрдсэн вектороор үржүүлэхэд шинэ координатууд ба нэгжээс бүрдсэн шинэ вектор гарна:

$$\begin{pmatrix} x & y & z & 1 \end{pmatrix} \cdot \begin{pmatrix} a_{11} & a_ {12} & a_ {13} & a_ {14} \\ a_{21} & a_ {22} & a_ {23} & a_ {24} \\ a_{31} & a_ {32} & a_ {33} & a_ {34} \\ a_{41} & a_ {42} & a_ {43} & a_ {44} \end{pmatrix} = \begin{pmatrix} x' & y' & z' & 1 \end{pmatrix}$$

(Яагаад зохиомол дөрөв дэх координат оруулав гэж асууж байна уу? Энэ бол компьютер график дээр өргөн хэрэглэгддэг нэгэн төрлийн координат-ын гоо сайхан юм. Үүнгүйгээр шилжүүлэх үйлдэл мэтийн аффин үйлдлийг ганц матриц үржүүлэлт хэлбэрээр илэрхийлэх боломжгүй, учир нь координат дээр тогтмол нэмэх шаардлагатай болдог. Аффин хувиргалт нь илүү өндөр хэмжээст шугаман хувиргалт болж хувирдаг!)

Хувиргалтуудыг матриц хэлбэрээр хэрхэн илэрхийлэх зарим жишээ:

Шилжүүлэх үйлдэл: $x$ координатыг $5$-аар, $y$ координатыг $7$-оор, $z$ координатыг $9$-өөр шилжүүлнэ.

$$\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 5 & 7 & 9 & 1 \end{pmatrix}$$

Масштаблах үйлдэл: $x$ координатыг $10$ дахин, нөгөө хоёрыг $5$ дахин масштаблана.

$$\begin{pmatrix} 10 & 0 & 0 & 0 \\ 0 & 5 & 0 & 0 \\ 0 & 0 & 5 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}$$

Эргүүлэх үйлдэл: баруун гарын дүрмийн дагуу (цагийн зүүний эсрэг чиглэлд) $x$ тэнхлэгийг тойруулан $\theta$ градусаар эргүүлнэ.

$$\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & \cos \theta & -\sin \theta & 0 \\ 0 & \sin \theta & \cos \theta & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}$$

Ингээд хувиргалт бүрийг матрицаар илэрхийлсний дараа, хувиргалтуудын дарааллыг эдгээр матрицуудын үржвэрээр, харин $k$ удаагийн давталтыг матрицыг $k$ зэрэгт дэвшүүлэх байдлаар илэрхийлж болно (үүнийг хоёртын зэрэгт дэвшүүлэлт ашиглан $O(\log{k})$-д тооцоолж болно). Ингэснээр бүх хувиргалтыг илэрхийлэх матрицыг эхлээд $O(m \log{k})$-д тооцоолж, дараа нь $n$ цэг бүр дээр $O(n)$-д хэрэглэснээр нийт $O(n + m \log{k})$ complexity-тэй болно.

Граф дахь $k$ урттай замын тоо¶

Бодлого: $n$ оройтой чиглэлтэй жингүй граф өгөгдсөн, дурын $u$ оройноос дурын $v$ орой хүрэх $k$ урттай замын тоог ол.

Шийдэл: Энэ бодлогыг тусдаа өгүүлэлд дэлгэрэнгүй авч үзсэн. Алгоритм нь графын adjacency matrix $M$-г ($m_{ij} = 1$ хэрэв $i$-ээс $j$ рүү ирмэг байвал, эсрэг тохиолдолд $0$ байх матриц) $k$ зэрэгт дэвшүүлэхээс бүрдэнэ. Ингэснээр $m_{ij}$ нь $i$-ээс $j$ рүү очих $k$ урттай замын тоо болно. Энэ шийдлийн time complexity нь $O(n^3 \log k)$.

Тэмдэглэл: Мөн тэр өгүүлэлд энэ бодлогын өөр нэг хувилбарыг авч үзсэн: ирмэгүүд жинтэй үед яг $k$ ирмэг агуулсан хамгийн бага жинтэй замыг олох шаардлагатай тохиолдол. Тэр өгүүлэлд үзүүлсний дагуу энэ бодлого мөн adjacency matrix-ыг зэрэгт дэвшүүлэх замаар бодогдоно. Матриц нь $i$-ээс $j$ рүү очих ирмэгийн жинг, эсвэл ийм ирмэг байхгүй бол $\infty$-г агуулна. Хоёр матрицыг үржүүлэх ердийн үйлдлийн оронд өөрчилсөн үйлдэл ашиглах ёстой: үржүүлэхийн оронд хоёр утгыг нэмж, нийлбэрийн оронд хамгийн багыг авна. Өөрөөр хэлбэл: $result_{ij} = \min\limits_{1\ \leq\ k\ \leq\ n}(a_{ik} + b_{kj})$.

Хоёртын зэрэгт дэвшүүлэлтийн хувилбар: хоёр тоог $m$ модулиар үржүүлэх¶

Бодлого: $a$ ба $b$ хоёр тоог $m$ модулиар үржүүл. $a$ ба $b$ нь стандарт өгөгдлийн төрөлд багтана, гэвч тэдгээрийн үржвэр нь 64 битийн бүхэл тоонд багтахааргүй том. Санаа нь $a \cdot b \pmod m$-г том тооны арифметик ашиглалгүйгээр тооцоолох явдал юм.

Шийдэл: Бид дээр тайлбарласан хоёртын байгуулалтын алгоритмыг үржүүлэлтийн оронд нэмэлт хийж хэрэглэнэ. Өөрөөр хэлбэл бид хоёр тооны үржүүлэлтийг $O (\log m)$ удаагийн нэмэх болон хоёр дахин нэмэгдүүлэх (энэ нь үндсэндээ нэмэх үйлдэл) үйлдэл болгон "задалсан".

$$a \cdot b = \begin{cases} 0 &\text{хэрэв }a = 0 \\ 2 \cdot \frac{a}{2} \cdot b &\text{хэрэв }a > 0 \text{ ба }a \text{ тэгш} \\ 2 \cdot \frac{a-1}{2} \cdot b + b &\text{хэрэв }a > 0 \text{ ба }a \text{ сондгой} \end{cases}$$

Тэмдэглэл: Энэ бодлогыг хөвөгч цэгтэй тооны үйлдэл ашиглан өөр аргаар бодож болно. Эхлээд $\frac{a \cdot b}{m}$ илэрхийллийг хөвөгч цэгтэй тоо ашиглан тооцоолж, түүнийг тэмдэггүй бүхэл тоо $q$ болгон хөрвүүлнэ. Дараа нь $a \cdot b$-ээс $q \cdot m$-г тэмдэггүй бүхэл тооны арифметик ашиглан хасаж, $m$ модулиар авснаар хариуг олно. Энэ шийдэл нэлээд найдваргүй харагдавч маш хурдан бөгөөд хэрэгжүүлэхэд амархан. Дэлгэрэнгүйг эндээс үзнэ үү.