Help in SEGPROD

help
, , ,
1

I was trying to solve the first two subtasks of SEGPROD but it was giving me NZEC everytime. I don’t know what made the program crash. Please help me debug it.

I am using the following logic to answer all the queries:

Let N = Product of all elements (from 1 to N ) (modulo P)
Let L = prefix product upto L-1 (modulo P)
Let R = suffix product from R+1 (modulo P)

Answer = (N * modularInverse(Q) * modularInverse(R)) (modulo P);

I tested this logic for sample inputs and some other Test Cases and it was giving correct output.

For first subtask P was prime and all the numbers were between 1 & P-1. So using MMI I could have got atleast 20 points. I am using Fermats’s little theorem to find MMI.

Here is the link to my solution using recursive version of it.

And here is the link to my solution with iterative version of it.

But they both are giving NZEC for reasons unknown to me.

I also used another method to find MMI mentioned here by Anveshi Shukla. But still the same results. Here is the link to that code.

Now for Subtask 2: P = x^k where x is prime and all the numbers are in range 1 to P-1. So I tried using Extended Euclidean algorithm to find MMI of numbers as it works when number and P are co-prime. This holds for both the subtasks and should atleast pass them. Here is the link to it.

The normal version of the code by by doing multiplication everytime for all the queries giving TLE is here. The code works fine. I just replaced running the loop everytime by the method mentioned above which gives result in constant time for each query. I can’t understand what is wrong with my MMI codes. Please help.

2

In almost every version of your answer there is Integer Overflow resulting in a wrong track for the answer. For some cases it caused RE.

 x = (sum * pre * suf) % P;

This line in your code (present twice) is causing the overflow.
Replace it by -

 x = (((sum * pre)%P) * suf) % P;

Do that and you will get AC for subtask #1. :slight_smile: (And remember to take mod in each step)

For subtask #2 this logic won’t work as A[i] and P might not be co-prime and hence don’t have a modular multiplicative inverse.

4 Likes
3

Nicely explained, bro ! :slight_smile: @trijeet

1 Like
4

Thank you. I can’t believe I did such a silly mistake. I was very careful for overflow’s and checked for each and every calculation except for this one. I am so angry with myself. I was changing MMI finding techniques while the error was in calculating x.

5

And for subtask 2 will the chinese remainder theorem solve the subtask or anything else?

6

Read @taran_1407’s appraoch from his psot. Nothing like CRT needed.

7

I too tried messing with CRT first. :slight_smile:

PS:Thanks for referral @vijju123. And Nicely answered @trijeet