Бінарне піднесення у степінь

Бінарне (двійкове) піднесення у степінь - це алгоритм, що дозволяє підносити будь-яке число в $n$-у степінь за $O(\log n)$ множень (замість $n$ множень при звичайному підході).

Крім того, описаний тут алгоритм можна застосувати для будь-якої асоціативної операції, а не тільки для множення чисел. Нагадаємо, операція називається асоціативною, якщо для будь-яких $a, b, c$ виконується:

$$(a \cdot b) \cdot c = a \cdot (b \cdot c)$$

Найчастіше використовується узагальнення - обчислення остачі за деяким модулем (асоціативність також зберігається). Наступним за частотою використання є узагальнення на добуток матриць (асоціативність загальновідома).

Алгоритм

Зауважимо, що для будь-якого числа $a$ і парного числа $n$ виконується тотожність (випливає з асоціативності операції множення):

$$a^n = (a^{n/2})^2 = a^{n/2} \cdot a^{n/2}$$

Вона і є основною в методі бінарного піднесення у степінь. Дійсно, для парного $n$ ми показали, як, витративши всього лиш одну операцію множення, можна звести до задачі з вдвічі меншим степенем.

Залишилося зрозуміти, що робити, якщо степінь $n$ непарна. Тут все дуже просто: перейдемо до степені $n-1$, яка вже буде парною:

$$a^n = a^{n-1} \cdot a$$

Отже, ми фактично знайшли рекурентну формулу: від степені $n$ ми переходимо, якщо вона парна, до $n/2$, а інакше - до $n-1$. Зрозуміло, що всього буде не більше $2 \cdot \log n$ переходів, перш ніж ми прийдемо до $n = 0$ (до бази рекурентної формули). Таким чином, ми отримали алгоритм, що працює за $O(\log n)$ множень.

Реалізація

Рекурсивна реалізація:

int binpow(int a, int n) {
    if (n == 0) {
        return 1;
    } else if (n % 2 == 1) {
        return binpow(a, n-1) * a;
    } else {
        int b = binpow(a, n/2);
        return b * b;
    }
}

Нерекурсивна реалізація із оптимізованими діленнями на 2, які замінені бітовими операціями:

int binpow(int a, int n) {
    int res = 1;
    while (n) {
        if (n & 1) {
            res *= a;
            --n;
        } else {
            a *= a;
            n >>= 1;
        }
    }
    return res;
}

Цю реалізацію можна ще трішки оптимізувати, помітивши, що піднесення $a$ в квадрат здійснюється завжди, незалежно від того, спрацювала умова непарності $n$ чи ні:

int binpow(int a, int n) {
    int res = 1;
    while (n) {
        if (n & 1) {
            res *= a;
        }
        a *= a;
        n >>= 1;
    }
    return res;
}

Також, варто підмітити, що бінарне піднесення у степінь вже реалізовано у мові Java, але тільки для класу з довгою арифметикою BigInteger (функція pow цього класу працює використовуючи описаний алгоритм).

Застосування

Ефективне обчислення чисел Фібоначчі

Умова. Дано число $n$. Потрібно обчислити $F_n$, де $F_i$ - послідовність чисел Фібоначчі.

Розв'язок. Більш детально цей розв'язок описано у статті про послідовності Фібоначчі. Тут ми лише коротко наведемо його суть.

Основна ідея наступна. Обчислення чергового числа Фібоначчі базується на знанні двох попередніх чисел Фібоначчі: а саме, кожне наступне число Фібоначчі обчислюється як сума двох попередніх. Це означає, що ми можемо побудувати матрицю $2 \times 2$, яка буде відповідати наступному перетворенню: як маючи два числа Фібоначчі $F_i$ та $F_{i+1}$ обчислити наступне число, тобто перейти до пари $F_{i+1}$, $F_{i+2}$. Застосовуючи це перетворення $n$ раз до пари $F_0$ та $F_1$, ми отримаємо пару $F_n$ і $F_{n+1}$. Таким чином, підносячи матрицю цього перетворення в $n$-у степінь, ми знайдемо шукане $F_n$ за час $O(\log n)$, що нам і було потрібно.

Піднесення перестановки в $k$-у степінь

Умова. Дано перестановку $p$ довжини $n$. Потрібно піднести її в $k$-у степінь, тобто знайти, що вийде, якщо до тотожної перестановки $k$ раз застосувати перестановку $p$.

Розв'язок. Застосуємо до перестановки $p$ описаний вище алгоритм бінарного піднесення у степінь. Жодних відмінностей із піднесенням чисел у степінь немає. Одержуємо розв'язок з асимптотикою $O(n \cdot \log k)$.

Зауваження

Дану задачу можна розв'язати ефективніше - за лінійний час. Для цього достатньо виділити у перестановці всі цикли, після чого розглянути окремо кожний цикл і, взявши $k$ за модулем довжини поточного циклу, знайти відповідь для цього циклу.

Швидке застосування набору геометричних операцій до точок

Умова. Дано $n$ точок $p_i$ та $m$ перетворень, які треба застосувати до кожної з цих точок. Кожне перетворення - це або переміщення на заданий вектор, або масштабування (множення координат на задані коефіцієнти), або обертання навколо заданої осі на заданий кут. Крім того, є складена операція циклічного повторення, яка має вигляд - "повторити задане число раз заданий список перетворень" (операції циклічного повторення можуть вкладатися один в одного).

Потрібно обчислити результат застосування заданих операцій до всіх точок за час, менший ніж $O(n \cdot length)$, де $length$ - загальна кількість операцій, які необхідно зробити.

Розв'язок. Розглянемо різні види перетворень з точки зору того, як вони змінюють координати:

• Операція переміщення - додає до всіх координат одиницю, помножену на деякі константи.
• Операція масштабування - множить кожну координату на деяку константу.
• Операція обертання навколо осі - нові координати можна записати у вигляді лінійної комбінації старих. Наприклад, у вигляді комбінації п'яти двовимірних поворотів: спочатку в площинах $OXY$ і $OXZ$ так, аби вісь обертання співпала з додатнім напрямом осі $OX$, потім необхідний поворот навколо осі в площині $YZ$, потім зворотні повороти в площинах $OXZ$ і $OXY$ так, аби вісь обертання повернулась у своє вихідне положення.

Кожне з цих перетворень - це переобчислення координат за лінійними формулами. Таким чином, будь-яке таке перетворення можна записати у вигляді матриці $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}.$$

Зауваження

Для чого введено фіктивну четверту координату, що завжди рівна одиниці? Без цього не вийшло б реалізувати операцію переміщення, адже переміщення - це як раз доданок до координат одиниці, що помножена на деякі коефіцієнти. Без фіктивної одиниці ми б змогли тільки реалізовувати лінійні комбінації самих координат, а додавати до них задані константи - не змогли б.

Тепер розв'язок задачі стає простим. Оскільки кожна елементарна операція описується матрицею, то послідовність операцій описується добутком цих матриць, а операція циклічного повторення - піднесення цієї матриці у степінь. Таким чином, ми за час $O(m \cdot \log repetition)$ можемо заздалегідь обчислити матрицю $4 \times 4$, що описує всі перетворення, і потім просто помножити кожну точку $p_i$ на цю матрицю - тим самим, ми дамо відповідь на всі запити за час $O(n)$.

Кількість шляхів фіксованої довжини у графі

Умова. Дано неорієнтований граф $G$ з $n$ вершинами, і дано число $k$. Потрібно для кожної пари вершин $i$ і $j$ знайти кількість шляхів між ними, що містять рівно $k$ ребер.

Розв'язок. Більш детально цю задачу розглянуто у окремій статті. Тут лише описано суть цього розв'язку: ми підносимо в $k$-у степінь матрицю суміжності цього графа, і елементи цієї матриці будуть мати шукані значення. Асимптотика - $O(n^3 \cdot \log k)$.

Зауваження

У згаданій статті розглядається також й інший варіант цієї задачі: коли граф зважений, і потрібно знайти шлях мінімальної ваги, що містить рівно $k$ ребер. Дана задача також вирішується за допомогою бінарного піднесення у степінь матриці суміжності графа, однак замість звичайної операції перемноження двох матриць використовують модифіковану: замість множень береться сума, а замість підсумовування - взяття мінімуму.

Добуток двох чисел за модулем

Умова. Дано два додатних цілих числа $a$ і $b$. Потрібно знайти значення їх добутку за модулем $m$:

$$a \cdot b \pmod m$$

Припустимо, що числа можуть бути достатньо великі: настільки, що самі числа поміщаються у базові типи даних, а ось їх добуток $a \cdot b$ - вже ні (відзначимо, що нам також буде потрібно, аби сума чисел поміщалась у базові типи даних). Відповідно, задача в тому, щоб порахувати шукану величину $(a \cdot b) \pmod m$, не застосовуючи довгу арифметику.

Розв'язок. Застосуємо алгоритм бінарного піднесення, описаний вище, тільки замість операції множення ми будемо використовувати додавання. Іншими словами, перемноження двох чисел ми звели до $O(\log m)$ операцій додавання і множення на два (що теж, по суті, є додавання).

$$f(a, b) = \begin{cases} 0 &\text{якщо }a = 0 \\\\ f(\frac{a}{2}, 2 b) &\text{якщо }a > 0 \text{ і }a \text{ парне} \\\\ f(\frac{a-1}{2}, 2 b) + b &\text{якщо }a > 0 \text{ і }a \text{ непарне} \end{cases}$$

Реалізація:

int binprod_mod(int a, int b, int m) {
    int res = 0;
    a %= m;
    b %= m;
    while (a) {
        if (a & 1) {
            res = (res + b) % m; 
        }
        b = (2 * b) % m; 
        a >>= 1;
    }
    return res;
}

Зауваження

Дану задачу можна розв'язати і по-іншому, використавши операції над числами з рухомою точкою. А саме, порахуємо в числах з рухомою точкою вираз $a \cdot b / m$, і заокруглимо його до найближчого цілого числа. Так ми знайдемо приблизну частку. Віднявши її від добутку $a \cdot b$ (проігнорувавши переповнення), ми, швидше всього, отримаємо деяке невелике число, яке можна взяти за модулем $m$ і повернути результат в якості відповіді. Цей розв'язок виглядає досить надійним та швидким і він дуже коротко реалізується.

Задачі

• Codeforces - 630 - Parking Lot

• Online Judge - 374 - Big Mod | Розв'язки: C++, Go, Python

• Spoj - LASTDIG - The last digit | Розв'язки: C++, Python