We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Mathematics
  3. Fundamentals
  4. Matrix Tracing
  5. Discussions

Matrix Tracing

Sort by

recency

|

52 Discussions

|

  • adrien_cordonni1
     + 0 comments

    For those interested, the technique needed to solve this exercises is close to the implementation of math.comb in the Python standard library (albeit using modulo 2⁶⁴ which comes for free if using unsigned integers). You can watch Raymond Hettinger's keynote "Numerical Marvels Inside Python" for more explanations.

  • haricung
     + 0 comments

    TLE'd on this but i was thinking somewhere along the lines of the followng: nc = int(math.factorial(m)//(math.factorial(r)*math.factorial(m-r))) where r in range(n)

  • macdonald_l_kyn
     + 0 comments

    My python3 solution but time limit execution

    def solve(n):
    if n == 0:
        return 1
    i = 5
    while True:
        if (n*"0") in str(math.factorial(i)):
            return i
        i += 1

  • stzong1
     + 1 comment
    import math
import os
import random
import re
import sys

mod = 10**9 + 7
    
def getfactmod(b):
  val = 1
  for i in range(1,b):
    val =((val%mod)*((i+1)%mod))%mod
  return val
    
def getpowermod(a,b):
    result = 1
    while b:
        if b%2 == 1:
            result = (result%mod * a%mod) % mod
        a = a%mod * a%mod
        b = b//2
    return result
        
def solve(x,y):
    num = getfactmod(x+y-2)
    denom = getfactmod(x-1)*getfactmod(y-1)
    return ((num%mod)*(getpowermod(denom,mod-2)))%mod
  
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(input().strip())

    for t_itr in range(t):
        first_multiple_input = input().rstrip().split()

        n = int(first_multiple_input[0])

        m = int(first_multiple_input[1])

        result = solve(n, m)

        fptr.write(str(result) + '\n')

    fptr.close()

  • soumyadipmandal2
     + 1 comment

    As there involves many large numbers in each test case, so applying the formula C ( m+n-2, m-1) or C (m+n-2, n-1) directly will not work.

    We have to use a bit of number theory here.

    To find the factorial of a number, n!, instead from 1 to n, we also have to mod put the value at each step of multiplication so that the multiplication becomes fast.

    According to fermat's little theorem, a ** ( p - 1 ) == 1 mod( p )

    ==> ( a ** ( p - 1 ) ) * ( a ** ( -1 )) == a ** ( -1 ) mod( p )

    ==> a ** ( p - 1 - 1 ) == a ** ( -1 ) mod( p )

    ==> a ** ( p - 2 ) == a ** ( -1 ) mod( p )

    ==> a ** ( -1 ) == a ** ( p - 2 ) mod( p )