red_coder's blog

fastest factorial....
By red_coder, 14 years ago, In English

suppose for any 'n' taken as input we want to output (2n)!/n!(n+1)! modulo 1000000007 then which is the fastest way to accomplish this task......

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

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

You can try to find a recurrence relation for your formula, then use matrix multiplication method to calculate Nth element of the sequence described by that recurrence relation.

→ Reply
  • »
    »
    14 years ago, hide # ^ |
    ← Rev. 3  
    Vote: I like it 0 Vote: I do not like it

    Can you calculate this faster than ?

    → Reply
    • »
      »
      »
      14 years ago, hide # ^ |
       
      Vote: I like it +2 Vote: I do not like it

      And how to calculate it for n / (log^2(n)) ?

      → Reply
    • »
      »
      »
      14 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it -9 Vote: I do not like it

      I'm not sure whether it is possible or not, but for example let's take the vector V = (n!, 0) and matrix M.

      M =

      V × M(n + 1) = V0 = (n!, (n + 1)!)

      Let's take another matrix P.

      P =

      V0 × P = ((n + 1)!, 0)

      So it means that (n!, 0) × M(n + 1) × P = ((n + 1)!, 0)

      I mean to use something similar to multiply by matrix in logN time.

      → Reply
      • »
        »
        »
        »
        14 years ago, hide # ^ |
         
        Vote: I like it +5 Vote: I do not like it

        I think it's not possible, because the formula is non linear.

        → Reply
        • »
          »
          »
          »
          »
          14 years ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          Actually , which is not linear, but it can be represented in the following linear recurrence relation:

          C(n, k) = C(n - 1, k) + C(n - 1, k - 1)

          → Reply
          • »
            »
            »
            »
            »
            »
            14 years ago, hide # ^ |
             
            Vote: I like it +5 Vote: I do not like it

            I mean if we talk about Fibonacci numbers we have vector (f[n], f[n — 1]) and the next vector can be obtained multiplying it with constant matrix. In this case we can have (n!, n) but next vector is (n!*(n+1), n+1). The second element is OK, but to produce first one we need to multiply v[0] and (v[1] + 1). That is what i call non-linear formula.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              14 years ago, hide # ^ |
               
              Vote: I like it -16 Vote: I do not like it

              But there is a way to calculate C(n, i) in O(N) time.

              where r — row, c --column

              source: wikipedia

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                14 years ago, hide # ^ |
                 
                Vote: I like it +13 Vote: I do not like it

                n! can be calculated in O(n). congratulations.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  14 years ago, hide # ^ |
                   
                  Vote: I like it +2 Vote: I do not like it

                  Not n! I mean v_c = \choose{n}{c}

                  So, we will get C(n, 0), C(n, 1), C(n, 2), ..., C(n, n) in O(N) time. Without using pascal's triangle or smth else.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  14 years ago, hide # ^ |
                   
                  Vote: I like it 0 Vote: I do not like it

                  c[n][k] = n!/((n-k)!k!).

                  → Reply
»
14 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

(2n)!/n!(n+1)! = 2^n / (n + 1). 2^n requires O(log n) time and 1 / (n + 1) % M is simply (n + 1)^(M — 2) % M (where M = 1000000007) because M is prime. So the total complexity is log M + log n which is fast enough I think

→ Reply
»
14 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

Btw, (2n)!/n!(n+1)! is the n-th Catalan number. So the problem of it's calcilation must be well known. Am I wrong?

→ Reply
»
14 years ago, hide # |
 
Vote: I like it -6 Vote: I do not like it

(2n)!/n!(n+1)!= c(2n,n)/(n+1)= c(2n,n)*(n+1)^(1000000005) Is it enough for you?:)

→ Reply
»
14 years ago, hide # |
← Rev. 4  
Vote: I like it 0 Vote: I do not like it

I think there is the way to precalculate some numbers, and then answer the queries fast enough. There is only one test case? or many queries to find n-th Catalan number? we need to find all prime numbers between 1 and mod, and some additional information.

→ Reply