spookywooky's blog

By spookywooky, history, 6 years ago, In English

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
        }
    }
}

'

  • Vote: I like it
  • +14
  • Vote: I do not like it

| Write comment?
»
6 years ago, # |
  Vote: I like it +27 Vote: I do not like it

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.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    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.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      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.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        What do you mean by using doubles?

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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?

            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
              Rev. 2   Vote: I like it +1 Vote: I do not like it

              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.

              • »
                »
                »
                »
                »
                »
                »
                »
                5 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 years ago, # ^ |
                  Rev. 3   Vote: I like it 0 Vote: I do not like it

                  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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Oh yea that makes sense, thanks!

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          KNow the answer?

          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            Wow, between the contest asking for solution which is relevant to a problem in contest is not legal!

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks. It helped :)

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by spookywooky (previous revision, new revision, compare).

»
5 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

I'm very confused about "if q==0,why I should print 0"

Since 0 have no inverses

»
4 years ago, # |
  Vote: I like it +43 Vote: I do not like it

I've wrote up a description of how this works. Here it is. Perhaps it will be useful.