[Guidance]How to solve this problem ?

suraj Unacademy Subscription
, , , , ,
1

I am working on this problem . As I am a newbie in algorithm designing , I wanted to know how can we solve this problem. Please help me in figuring this out in brief.

P.S. - A tutorial can be a great help for many other people like me who wants to learn.

Thanks In Advance.

2

What you have to do is find n!(k!(n-k)!)^-1 right,

  • first make an array to store all factorials of i. do a[i]=(a[i-1]*i)%mod
  • then using fermats theorm do a[k]^-1 and a[n-k]^-1 (a[k]^-1 % mod = a[k]^mod-2 %mod, do with modular exponentiation)
  • then multiply these two with a[n] and take mod
  • also if n<k print 0

here is the code : click here

1 Like
3

How did you write the power function? I don’t understand it.

4

@king_of_hacker,can you tell me when the fermats test can be used;if a[n] is divisible by Mod and ans of total combination value (a[n]/(a[k]*a[n-k]))%Mod gives some non zero value then how to get through that case? if we do by your way it gives zero ans in that case as we are separtaely calculating mod of each and multiplying;so ifa[n]%mod=0,then whole will become zero.I am a newbie,Sorry if any conceptual mistakes are on my side.

1 Like
5

Editorial for the problem

1 Like
6

cool, mod here is 10^9+7 which is prime, so a[n]%mod wont be zero, because for a[n] to be divisible by mod, a[n] should be mod!(factorial). That’s why mod will be a prime number most of the times.

7

this is a common technique called modular exponentiation https://en.wikipedia.org/wiki/Modular_exponentiation

8

Got it.Thank you.