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

×

# [Guidance]How to solve this problem ?

 0 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 240●3●9●32 accept rate: 5%

 1 answered 29 Jun '15, 19:11 439●14 accept rate: 16%
 1 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
 1 @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 128●7 accept rate: 8% 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) Got it.Thank you. (30 Jun '15, 16:24)
 toggle preview community wiki:
Preview

### Follow this question

By Email:

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

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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,738
×1,918
×1,491
×713
×159
×6

question asked: 29 Jun '15, 01:55

question was seen: 1,297 times

last updated: 30 Jun '15, 16:24