- Prepare
- Mathematics
- Fundamentals
- Matrix Tracing
- Discussions
Matrix Tracing
Matrix Tracing
+ 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)
+ 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
+ 0 comments 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()
+ 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 )
+ 1 comment i found a very easy answer......fact(r+c-2)/(fact(r-1)*fact(c-1))...............can someone verify
Sort 51 Discussions, By:
Please Login in order to post a comment