stropr problem python

general
1

Here is the problem link:
link text

As mentioned in the STROPR editorial, I’m calculating the coefficients by

(M+3)!/ (4! * (M-1)! ) = M*(M+1)(M+2)(M+3)/4!

So, here is my code link:
link text

Here’s what I’m doing:
I’m going backwards from x.
Every loop, I calculate product = product * (M + extra) / (extra)
and then the total sum is stored in sums as sums = sums + Ax * product
and as the loop goes, the extra is incremented by one.
And then the output is sums % 1000000007

Subtasks 1 and 2 ran perfectly. But, it gave TLE in the 3rd subtask.
I don’t know where I’m making any mistake. I think that I’m using the least loops required to calculate the sum, but clearly I’m doing something wrong. Would someone please guide me in the right direction? Thanks, in advance.

2

The result can be a really huge number. So big that even multiplying 2 numbers gets slow.

You should have used the modulo in the intermediate calculations to keep the numbers small.

2 Likes
3

product = product * (M + extra) / (extra)
Here actually you should calculate the multiplicative inverse of 1/extra with respect to MOD(10**9 +7)
link text
Hope it helps, cheers!

1 Like
4

First no need to store the answer of each test case in out list , directly print it in the loop itself,

And multiplying big numbers can get slow , so use mod the sum by (10**9 + 7) in each step to keep the results small.

5

Thanks man. First I started calculating the modulo before multiplying two numbers, but it still wouldn’t help. Then I tried the multiplicative inverse, and after a bit of research, it worked.