XOR_EQUALITY precompute

help
1

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 ?

2

this is problem link

3

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

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?

6

Yes

It will be O(\log N)

1 Like
7

Thank you very much!