You are not logged in. Please login at www.codechef.com 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

2★shubham99
2403932
accept rate: 5%


link

answered 29 Jun '15, 19:11

geek_geek's gravatar image

4★geek_geek
43914
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

link

answered 29 Jun '15, 12:39

king_of_hacker's gravatar image

3★king_of_hacker
204312
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 https://en.wikipedia.org/wiki/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.

link

answered 29 Jun '15, 16:54

manjunath1996's gravatar image

4★manjunath1996
1287
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
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×2,700
×1,901
×1,470
×703
×127
×6

question asked: 29 Jun '15, 01:55

question was seen: 1,287 times

last updated: 30 Jun '15, 16:24