Working with fractions usually we get a hint like "You should compute P⋅Q−1 modulo 109+7, where Q−1 denotes the multiplicative inverse of Q modulo 109+7."
So, I more (or less) understood what that means. I can express, say 1/5 by the number 400000003. I can calculate that number using https://www.geeksforgeeks.org/fermats-little-theorem/ implemented by some code I found somewhere (see below).
BUT: How do I add (and/or multiply) fractions with huge values?
i.e. how to calculate and express something like this: Let E=10e9+7 Then, how to express: ((E+1) / (E+2)) + ((E+3) / (E+4))
Any hint or link to an understandable explenation would be really helpfull. Thanks.
The code I use so far, based on that fermat thing: ' class Inv { companion object { val defaultMod = 1000000007L var MOD = defaultMod
fun toPower(a: Long, p: Long, mod: Long = MOD): Long { var a = a var p = p var res = 1L while (p != 0L) { if (p and 1 == 1L) res = res * a % mod p = p shr 1 a = a * a % mod } return res } fun inv(x: Long, mod: Long = MOD): Long { return toPower(x, mod - 2) } fun simpleInf(nenner: Long, zaehler: Long): Long { return nenner * Inv.inv(zaehler) % Inv.MOD } } }
'
It's pretty simple. Want to add (1/5) mod M and (1/6) mod M? Compute their values (if M = 1e9+7: 400000003, 166666668), add them together, and then mod.
It's the same for multipying.
Thanks, that works fine!
Further more I found that at subtraction, I need to add M to the result if less than 0, then applying mod if bigger than M.
But what if we want to compare the maximum of two fractions, can we do it by storing PQ - 1modN.
Addition is pretty clear, but in some DP questions we may also want to store maximum from two previous states where previous states contatins probability, can we store in this form and still do this comparision?
It will overflow if they get way too big, and you can't store modded versions of them, so no. I haven't seen a single DP question requiring this. Maybe they can be solved by greedy or another algorithm, give me an example.
If previous states store probabilities, then you shouldn't be storing them under a modulo anyways, and instead use doubles. So, atleast this case shouldn't occur in practice.
What do you mean by using doubles?
Sorry if it was unclear. By "double"(s) I meant the data type "double", which stores real numbers as compared to the usual "int" or "long long int" data type which store integers.
The problem I'm facing is, I need to store probabilities of previous states in dp to calculate current state and in the end output probability in the form P.Q^-1 %mod where P and Q are co prime.
In such a scenario what would be the best to store in a dp? The numerator of the number ?(in this case how to make P and Q coprime?) or P.Q^-1 %mod of the current state?
Since they require $$$P/Q (mod M)$$$, then you can't use doubles, because of precision error ( modulo enforces you to be exact with the calculations ).
In general, in these questions, you should look at probability like this $$$Probability( Event A ) = \dfrac{\text{# times A occurs}}{\text{Total number of scenarios}}$$$. So, your $$$dp$$$ should calculate $$$\text{Number of ways of something happening}$$$, and at the end, divide by total scenarios. ( Note: divide here means multiplying by modular inverse ).
Now, to calculate $$$P/Q ( mod M )$$$, we need what is known as modular inverse of $$$Q$$$. Modular Inverse of $$$Q$$$ under modulo $$$M$$$ ( say $$$X$$$ ), is such a number that $$$ X*Q ( mod M ) = 1 $$$. Read more here.
In that case how can we ensure that P and Q are coprime? According to you number of ways can be stored in the dp and progressively we can find the numerator P using dp. And Q will be total number of scenarios which can be calculated.
But by finding P and Q seperately how can we ensure they're coprime because 2*modinv(4)!=1*modinv(2).
I've been trying a question and I feel I'm getting a wrong answer due to this. I've tried everything at this point.
Well, you don't need to make $$$P$$$ and $$$Q$$$ coprime.
Proof: Let $$$P$$$ and $$$Q$$$ be not coprime, i.e. they have common factor, say $$$R$$$. Then $$$P = R*A$$$, $$$Q = R*B$$$. Now, $$$inv(Q) = inv(R)*inv(B)$$$
So, $$$P*inv(Q) = R*A*inv(R)*B = (R*inv(R))*A*inv(B) = (1)*A*inv(B) $$$. [ $$$inv(R)$$$ is modular inverse of $$$R$$$ ].
Also, $$$ 2 * modinv(4) = 1 * modinv(2) $$$. Because $$$ 4 * modinv(4) = 1 $$$, multiply $$$modinv(2)$$$ on both sides, that gives $$$ 2 * modinv(4) = modinv(2) $$$.
NOTE: All multiplications are assumed to be computed under the modulo $$$M$$$. I forgot to write it everywhere explicitly.
Oh yea that makes sense, thanks!
Could you help with how to evaluate p q-1 modulo M M is prime. Given that q = x^y and y can be as large as 10^6
KNow the answer?
Wow, between the contest asking for solution which is relevant to a problem in contest is not legal!
Thanks. It helped :)
Auto comment: topic has been updated by spookywooky (previous revision, new revision, compare).
I'm very confused about "if q==0,why I should print 0"
Since 0 have no inverses
I've wrote up a description of how this works. Here it is. Perhaps it will be useful.