XOR_EQUALITY precompute

Hey , I just saw the editorial of this question and I did not understand how pre-computation does not give TLE

Like even when we are precomputing we iterate through all the values and still use % 1e9 + 7

Is it that we face that only because of the calculation of 2^n and we avoid that by using
void pre(){
ans[1] = 1;
for(int i =2; i< MX ; i++)
ans[i] = (ans[i - 1] * 2) % MOD;

here MX is range of n and MOD is 1e9 + 7
The modulus operation doesn’t give TLE when working with large values like 1e9 + 7 ?

this is problem link

Why should it give a TLE, it a linear time computation which is feasible for N \le 10^5

so basically if we compute 2^(n-1)% (1e9 + 7) for every test case then complexity is O(2^n) and if we precompute it will be O(n) for precompute and then for every test case it will take O(1) time?


It will be O(\log N)

1 Like

Thank you very much!