Prefix Sums Quiz Question 4 (https://usaco.guide/silver/prefix-sums?lang=cpp#quiz)

[star911]

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.

[Benq]

@star911

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

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

@star911

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

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

@star911

<some numerator> mod M?

What does this mean?

@star911

I have basic knowledge of Modular (Modular Arithmetic · USACO Guide), but I’m not very aware about its properties.

This module is a prerequisite.

[star911]

Thanks @Benq.

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