Sateliti TLE

Debugging Help
#1

Problem Info

I’m doing Sateliti from the Gold string hashing module.

My Work

My code is here.
It follows the approach here, using binary search and hashing to find the first position at which the two images differ.
For the hash, it uses 2D prefix sums and a modular inverse.

The problem is, this only passes the first two subtasks. I’m not sure how to pass the last one- it seems that the constant factor of my program is simply too large.
Is there a clever way to avoid calculating modular inverses or something? It seems that precalculating the powers and inverses takes up an extremely large chunk of the runtime.

#2

I fixed it and it works now.
The optimization was not to not calculate the inverse, but to speed it up to \mathcal{O}(1) instead like so:

    vector<long long> pow2((row_num * 2) * (col_num * 2));
    vector<long long> pow2_mod_invs(pow2.size());
    pow2[0] = pow2_mod_invs[0] = 1;
    long long base_inv = mod_inv(2, MOD);
    for (int p = 1; p < pow2.size(); p++) {
        pow2[p] = pow2[p - 1] * 2 % MOD;
        pow2_mod_invs[p] = (pow2_mod_invs[p - 1] * base_inv) % MOD;
    }