You are not logged in. Please login at to post your questions!


[Guidance]How to solve this problem ?

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.

asked 29 Jun '15, 01:55

shubham99's gravatar image

accept rate: 5%


answered 29 Jun '15, 19:11

geek_geek's gravatar image

accept rate: 16%

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


answered 29 Jun '15, 12:39

king_of_hacker's gravatar image

accept rate: 7%

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

(29 Jun '15, 14:51) prrateekk3★

this is a common technique called modular exponentiation

(30 Jun '15, 14:11) king_of_hacker3★

@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.


answered 29 Jun '15, 16:54

manjunath1996's gravatar image

accept rate: 8%

edited 29 Jun '15, 17:08

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.

(30 Jun '15, 14:08) king_of_hacker3★

Got it.Thank you.

(30 Jun '15, 16:24) manjunath19964★
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 29 Jun '15, 01:55

question was seen: 1,297 times

last updated: 30 Jun '15, 16:24