Master0fPuppets's blog

By Master0fPuppets, history, 4 weeks ago, In English

Hi guys

Problem:https://codeforces.com/contest/1165/problem/E

I don't know why this solution (https://ideone.com/Q3bmkC) works and this (https://ideone.com/YJx6XI) doesn't

Both are the same idea the problem is just with the mod. I thought in the wrong solution that mod is distributed on multiplication so I didn't write (a[i]%mod *b[i]%mod) instead I wrote it as (a[i]*b[i])%mod so can someone explain it to me why this gave WA!

 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Mod is distributed on multiplication, the problem in your code is overflow, in your code has a for that make a[i] = a[i]"i*(n-i), so when you do the operation a[i]*b[i], you can have a number that is bigger then long long.

When we are dealing with numbers with mod, we need to guarantee that at any time of the code, the numbers will assume just values between 0 and $$$mod-1$$$, if you dont do that, you will probably get a overflow when doing a operation of multiplication, The choosen value of mod have a reason, they are around $$$10^9$$$, a multiplication of two values of this size is around $$$10^{18}$$$, which is near to the maximum value of long long