Prefix Sums Quiz Question 4 (

Hello All,

In the prefix sums challenge problem, it is mentioned:

Instead of adding, we multiply, and instead of subtracting, we divide

Am I correct to assume the following?

  1. Instead of adding, we multiply means that while calculating the Prefix Products array
    prefix[k] = prefix[k - 1] * arr[k]

  2. instead of subtracting, we divide means that the range product of subarray in indices [L,R] inclusive, will be prefix[R]/prefix[L - 1]

Also, does we calculate the answer modulo a given M mean that we will not use prefix[R]/prefix[L - 1] to find the range product of subarray, but will instead use something like <some numerator> mod M?

Actually I’m not able to get the correct answer, perhaps because I have not understood the question correctly. Could you please also let me know if I need any prerequisites for this question other than the Prefix Sums resource itself? I have basic knowledge of Modular (Modular Arithmetic · USACO Guide), but I’m not very aware about its properties.

prefix[k] = prefix[k - 1] * arr[k] % M

yes (assuming division means multiplying by modular inverse here, and then taking modulo M)

What does this mean?

This module is a prerequisite.

Thanks @Benq.

I’ll go through Modular Arithmetic and revert back if I still face problems.