Fast Power & Modulo

In one sentence

To compute \(a^b\) with a huge \(b\), square instead of multiply: \(a^{b} = (a^{b/2})^2\), so only about \(\log_2 b\) multiplications are needed, and taking % MOD after each one keeps the numbers small.

Where this comes from

This topic is the fourth problem set, 4-quick_power (March). We did not write a lesson note for it, so this page is written from scratch; the problems are the ones from that set.

1. What problem does it solve?

Example — 1228B · Filling the Grid (4-quick_power · B, rating 1400)

A grid has \(h\) rows and \(w\) columns; each cell is full or empty. You are told \(r_i\) = how many cells at the start of row \(i\) are full in a row (then an empty one, unless the row is completely full), and \(c_j\) = the same for column \(j\) from the top. Count the grids that match, modulo \(10^9 + 7\).

Limits: \(h, w \le 10^3\).

Input          Output
3 4
0 3 1
0 2 3 0        2

1 1
0
1              0

Step 1 (no power needed yet). Each \(r_i\) fixes some cells: the first \(r_i\) cells of row \(i\) are full and, if \(r_i < w\), cell \((i, r_i)\) is empty. Columns fix cells the same way. If a column wants a cell full that a row already made empty (or the other way round), the answer is \(0\).

Step 2. Every cell nobody fixed can be full or empty freely. With \(f\) free cells there are \(2^f\) grids, and \(f\) can be almost \(10^6\). We need \(2^f \bmod (10^9+7)\) fast.

2. The math

2.1 Modulo keeps numbers small

\((x \cdot y) \bmod m = \big((x \bmod m)\cdot(y \bmod m)\big) \bmod m\), and the same for \(+\). So we may take % MOD after every multiplication. Both factors are then below \(10^9 + 7\), their product is below \(1.1\cdot10^{18}\), which fits in long long.

2.2 Squaring halves the exponent

\[ a^b = \begin{cases} 1 & b = 0 \\ \left(a^{b/2}\right)^2 & b \text{ even} \\ a \cdot \left(a^{(b-1)/2}\right)^2 & b \text{ odd} \end{cases} \]

Each step halves \(b\), so there are at most \(\lfloor \log_2 b \rfloor + 1\) steps. For \(b = 10^{18}\) that is \(60\) steps instead of \(10^{18}\).

The loop version reads the bits of \(b\) from the right: keep a equal to \(a^{1}, a^{2}, a^{4}, a^{8}, \dots\) and multiply it into the result whenever the matching bit of \(b\) is \(1\).

2.3 Trace: \(3^{13}\)

\(13 = 1101_2 = 8 + 4 + 1\), so \(3^{13} = 3^8 \cdot 3^4 \cdot 3^1\).

bit of 13	a (= \(3^{2^k}\))	bit on?	res
1 (k=0)	3	yes	3
0 (k=1)	9	no	3
1 (k=2)	81	yes	243
1 (k=3)	6561	yes	1594323

\(3^{13} = 1\,594\,323\). Four multiplications into res, four squarings.

2.4 Trace on sample 1

Fixed cells (# full, . empty, ? free) after rows \(r = (0, 3, 1)\) and columns \(c = (0, 2, 3, 0)\):

row 0:  . # # .
row 1:  # # # .
row 2:  # . # ?

No conflict, one free cell, answer \(2^1 = 2\).

3. Template

Written in our usual style for this page:

const ll MOD = 1000000007;

// a^b mod MOD in O(log b)
ll power(ll a, ll b) {
    ll res = 1;
    a %= MOD;
    while (b > 0) {
        if (b & 1) {
            res = res * a % MOD;
        }
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

4. Worked solution — Filling the Grid

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

const ll MOD = 1000000007;

// a^b mod MOD in O(log b)
ll power(ll a, ll b) {
    ll res = 1;
    a %= MOD;
    while (b > 0) {
        if (b & 1) {
            res = res * a % MOD;
        }
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

void solve() {
    int h, w;
    cin >> h >> w;

    // g[i][j]: -1 free, 1 must be full, 0 must be empty
    vector<vector<int>> g(h, vector<int>(w, -1));
    for (int i = 0; i < h; i++) {
        int r;
        cin >> r;
        for (int j = 0; j < r; j++) {
            g[i][j] = 1;
        }
        if (r < w) {
            g[i][r] = 0;
        }
    }

    bool ok = true;
    for (int j = 0; j < w; j++) {
        int c;
        cin >> c;
        for (int i = 0; i < c; i++) {
            if (g[i][j] == 0) {
                ok = false;
            }
            g[i][j] = 1;
        }
        if (c < h) {
            if (g[c][j] == 1) {
                ok = false;
            }
            g[c][j] = 0;
        }
    }

    if (!ok) {
        cout << 0 << "\n";
        return;
    }

    ll f = 0;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (g[i][j] == -1) {
                f++;
            }
        }
    }
    cout << power(2, f) << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int T = 1;
    for (int i = 0; i < T; i++) {
        solve();
    }
    return 0;
}

5. Cousins: when the power repeats

Sometimes you do not even need fast power, because the values cycle. This is the "calculate at least 10 steps by hand and look for a pattern" advice from the 8 March lesson.

• 742A · Arpa's hard exam asks for the last digit of \(1378^n\). Only the last digit \(8\) matters: \(8, 4, 2, 6, 8, 4, 2, 6, \dots\) has period \(4\), and \(n = 0\) gives \(1\).
• 450B · Jzzhu and Sequences defines \(f_i = f_{i-1} - f_{i-2}\). Writing out \(x, y, y-x, -x, -y, x-y, x, y, \dots\) shows period \(6\). The answer can be negative, so print ((v % MOD) + MOD) % MOD (sample 2 prints \(10^9 + 6\) for \(-1\)).

6. Common mistakes

Overflow inside power

res * a must be computed on long long values that are already reduced below MOD. Forgetting a %= MOD at the start breaks this when a is large.

Negative numbers and %

In C++, -1 % MOD is -1. Add MOD before the final % whenever a subtraction happened.

pow(2, f) from <cmath>

pow works with double: it loses precision above \(2^{53}\) and does not know about the modulus. Always write your own power.

7. Practice

Problem	Set	Rating	Idea
742A · Arpa's hard exam and Mehrdad's naive cheat	4-quick_power · A	1000	last digit cycles with period 4
1228B · Filling the Grid	4-quick_power · B	1400	count free cells, \(2^f \bmod p\) (this page)
1097B · Petr and a Combination Lock	4-quick_power · C	1200	bitmask enumeration
450B · Jzzhu and Sequences	4-quick_power · D	1300	period 6 and a non-negative modulo

---

Credits & licenses

Everything on this page (explanation, traces, template, worked solution, mistakes) is ours. Problem statements are summarised; the originals are on Codeforces.