# Sherlock and Permutations

# Sherlock and Permutations

VamsiSangam + 17 comments The given problem is simple and reduces to -

**(N + M - 1)**!

--------------**(M - 1)! (N)!**

Now, let's keep it super simple and say, we put the Numerator in a variable '**Nr**' and the Denominator in a variable '**Dr**'. Now, we are supposed to calculate,

**(Nr / Dr) % P**, where '**P**' is the given prime**(10**^{9}+ 7)

We could write the above expression as,

**(Nr * Dr**,^{-1}) % P

Now we can apply the principle of modular arithematic,

**(a * b) % p = ((a % p) * (b % p)) % p**,

So, Applying the above principle, we get,

**(Nr * Dr**,^{-1}) % P = ((Nr % P) * (Dr^{-1}% P)) % P

Now, using Fermat's Little Theorem, we can replace the '**Dr**' term and the equation becomes,^{-1}

**(Nr * Dr**,^{-1}) % P = ((Nr % P) * (Dr^{(P - 2)}% P)) % P

Now, calculating**(Nr % P)**is simple, we use the above used modular arithematic principle, and the term**(Dr**can be calculated by using the technique stated in the link provided by the editorial.^{(P - 2)}% P)

But the problem is, that '**Dr**' over there, itself can be very big. We have techniques to calculate '**x**', but in our case this '^{y}% P**x**' is itself damn big. That is, our variable '**Dr**' itself can be something like, '**(499! * 500!)**' which we cannot calculate.

Then, my question is, what value will we insert in place of '**Dr**' in the term**(Dr**.....?? How can that be calculated...?? I've been trying to find that out since several weeks. This is my confusion in many problems, please please clarify...... Thanks in advance...! :-)^{(P - 2)}% P)abhiranjan + 0 comments Ohh dear!

`(a*b)%p == ((a%p)*(b%p)) % p => 5! % 7 = (1 * 2 * 3 * 4 * 5) % 7 = ((((1 * 2)%7 * 3)%7 * 4)%7 * 5)%7 = (((2 * 3)%7 * 4)%7 * 5)%7 = (((6 * 4)%7 * 5)%7 = (24%7 * 5)%7 = (3 * 5)%7 = 15%7 = 1`

VamsiSangam + 0 comments Yes abhiranjan Sir.... I understand that very well.... What asked was... Take a test case where M = 500, N = 500, that sums to,

(999!) / (499! * 500!)

Then our formula becomes,

((999!) / (499! * 500!)) % P = ((999! % P) * ((499! * 500!) (P - 2) % P)) % P,

The first term, (999! % P) can be calculated as you told Sir, but how do I calculate the next term,

**((499! * 500!) (P - 2) % P)**.....?? Can you please explain me mathematically step-by-step, exactly as you did above....??P.S. ..... Sir, the above mentioned content means EXACTLY the same as your answer to a discussion.... I got this same doubt when I tried to understand your answer, Sir.... But I could'nt, then I ignored.... But as too many Q's were demanding this technique, I had to ask... I hope you understand... Please clarify my confusion Sir.... Thanks a lot for the reply Sir...! :-)

abhiranjan + 3 comments So, in our next step we need the help of

*higher powers*, or we need to calculate*ab %m*.`= 1 % m , b == 0 a^b = a*(a^(b-1)) % m , odd b = a'^2 % m , even b where a' = a^(b/2)`

Suppose we need to calculate

*2100 % 11*.`2^100 = (2^50)^2 (mod 11) 2^50 = (2^25)^2 (mod 11) 2^25 = 2*(2^24) (mod 11) 2^24 = (2^12)^2 (mod 11) 2^12 = (2^6)^2 (mod 11) 2^6 = (2^3)^2 (mod 11) 2^3 = 2*(2^2) (mod 11) 2^2 = (2^1)^2 (mod 11) 2^1 = 2*(2^0) (mod 11) 2^0 = 1`

Now popping whole stack,

`2^1 = 2*1 = 2 (mod 11) 2^2 = 2^2 = 4 (mod 11) 2^3 = 2*4 = 8 (mod 11) 2^6 = 8^2 = 64 = 9 (mod 11) 2^12 = 9^2 = 81 = 4 (mod 11) 2^24 = 4^2 = 16 = 5 (mod 11) 2^25 = 2*5 = 10 (mod 11) 2^50 = 10^2 = 100 = 1 (mod 11) 2^100 = 1^2 = 1 (mod 11)`

hjm921028 + 0 comments thank you very much,it works!

coolrohan123 + 0 comments Sir please check my program , I am getting wrong answer . I have implemented your concept https://www.hackerrank.com/challenges/sherlock-and-permutations/submissions/code/18386949

dnlkotler + 1 comment I've been trying to use fast exponential method to calculate: (Dr)^(p-2). using recursion. but im getting run time error: Terminated due to time out. this is my function to the fast method:

static int fastPowerMethod(long num, long power, long mod) {

if (power==0) {

return 1;

}

else if (power%2==0) {

return (int)((fastPowerMethod(num, power/2, mod)**2)%mod);

}

else {

return (int)((num*fastPowerMethod(num, power-1, mod))%mod);

}

}

can you tell me if i did something wrong?

P.S the rest of the code works fine

*** edit ***

its works now - no "run time error: Terminated due to time out" occurs. but it doesnt work with the prime number 10^9 + 7. i tried some other small prime numbers (like 5,7,23,101...) and it worked for "Test 1", but not with 10^9+7... please help

Ooooscar + 0 comments I'm afraid that I have got the same problem. I implemented your Method "fastPowerMethod()" into my program, and it worked for "Test 1" even with the prime number 10^8+7, but it does not seem to work with 10^9+7... Could anyone explain why? Thanks a lot!

**--- edit ---**I just solved the problem myself, and it was due to "long" accidently converted to "int". P.S. The paragraph inside the quotation marks " */ /* " is an alternate solution not using recursion.

static int fastPowerMethod(int base, int exponent, int modulus) { if (exponent == 0) {return 1;} else if (exponent % 2 == 0) { long k = fastPowerMethod(base, exponent/2, modulus); return (int)((k * k) % modulus); } else { return (int)(((long)base * (long)fastPowerMethod(base, exponent-1, modulus)) % modulus); } /* int result = 1; while (exponent > 0) { if ((exponent % 2) == 1) { result = (int)(((long)result * (long)base) % modulus); } base = (int)(((long)base * (long)base) % modulus); System.out.println(exponent + ": " + result); exponent = exponent / 2; } return result; */ }

VamsiSangam + 0 comments Yes Sir, I understood that idea completely..... In your example you were able to calculate,

**2100 % 11**. But what if instead of that '**2**' over there, we had something like '**499! * 500!**'....??abhiranjan + 2 comments You need to calculate factorials using method posted in first reply.

`a = 499! (mod p) b = 500! (mod p) where, 0 <= a, b < p`

Now problem reduces to

`1/(a*b) = (a*b)^-1 (mod p) = c^-1 (mod p) = c^(p-2) (mod p) where, c = (a*b)%p`

Now use fast exponential method, posted in last reply, to calculate higher power.

sriv_shubham + 0 comments thanks sir...ur explanation helped to pass all test cases in 1st attempt....i always wanted to learn modular arithmetic on large numbers :)

Ooooscar + 0 comments Sir, your explanation was great, and it helped me understand your approach. But I want to point out that 1/(a*b) is not an integer, so I believe that mathematically it could be better understood, if written like this:

**( Nr / Dr ) % p****= ( Nr * 1 / Dr ) % p****= ( Nr * Dr^(p-1) / Dr) % p**(--> According to Fermat's Little Theorem,

**n^(p-1) = 1 (mod p)**, where n is an integer and p is a prime number, such that n is not divisible by p)**= ( Nr % p ) * ( Dr^(p-2) % p )**

VamsiSangam + 0 comments So, to calculate,

**(499! * 500!)(P - 2) % P**,if I store the value of,

**((499! % P) * (500! % P))**in a variable '**temp**', then my expression reduces to,**(temp)(P - 2) % P**,Am I right, Sir...??

abhiranjan + 1 comment Exactly.

mihirkarkare + 2 comments Sir, I am unable to understand how to slove this question. I have understood till the use of fermat's little theorem.

c=1; for(k=1;k<=n;k++) { c=((c%p)*(((n+m-k)%p)*(pow(k,p-2)%p)%p))%p; } //how do i compute pow(k,p-2)%p ?

levpolka + 0 comments Formula is (n+m-1)!/(n!*(m-1)!) 1. AL1 (ArrayList) contains integers from 2 to n+m-1. 2. AL2 contains integers from 2 to n and from 2 to m-1. 3. There is function returning list with primes (like it turns list {1 2 3 4 5 6} to {1 2 3 2 2 5 2 3}). 4. Delete from AL1 all elements which occur in AL2 (AL2 becomes empty). 5. Multiply all elements of AL1 by mod.

`public static void main(String[] args) { Scanner in = new Scanner(System.in); int t = in.nextInt(); while (t-- > 0) { int n = in.nextInt(); int m = in.nextInt(); ArrayList<Integer> list1 = new ArrayList<>(); ArrayList<Integer> list2 = new ArrayList<>(); for (int i = 2; i <= n + m - 1; i++) { list1.add(i); if (i <= n) list2.add(i); if (i <= m - 1) list2.add(i); } list1 = primeList(list1); list2 = primeList(list2); for (int i = 0; i < list2.size(); i++) list1.remove(list1.indexOf(list2.get(i))); long res = 1; int mod = (int) Math.pow(10, 9) + 7; for (int i = 0; i < list1.size(); i++) res = (res * list1.get(i)) % mod; System.out.println(res); } } public static ArrayList<Integer> primeList(ArrayList<Integer> list) { for (int i = 0; i < list.size(); i++) { ArrayList<Integer> primes = new ArrayList<>(); for (int j = 2; j <= (int) Math.sqrt(list.get(i)); j++) { if (list.get(i) % j == 0) { primes.add(j); list.set(i, list.get(i) / j); j--; } } list.addAll(primes); } return list; }`

ashwinkumare994 + 0 comments Klondike solitaire is one of the most popular online card game,players are so happy play klondike solitaire online free and inviting others to Join easily.

VamsiSangam + 0 comments Hey, it worked.... Thanks a lot for the help, Sir...! I've been trying to learn it since ages, finally got it...! :-)

Shishir_Singhal + 3 comments sir, please tell me how can you reduce Dr^-1 to Dr^(p-2) by using little fermat's theorem..?? sir , thanks for advance .....

KitFung + 0 comments [deleted]KitFung + 0 comments If a is not divisible by p

n! will not be a multiple of p if n > p and p is prime.

a^(p-1) % p= 1

Dr^-1 = (Dr^-1) * (1)

Dr^-1 % p = ((Dr^-1) * (Dr^(p-1)) ) % p

Dr^-1 % p = (Dr^(p-2)) % p

dnlkotler + 0 comments Little fermat's theorem applies: a^p = a (mod p), where p is prime number, a in Z and is not divided by p. so you can divide by a. division by a^2 gives you: a^(p-2) = a^-1 (mod p)

Shishir_Singhal + 0 comments [deleted]ahujashubham95 + 0 comments can you please explain the logic behind replacing Dr^(-1) with Dr^(p-2)??

pasupuletiganes1 + 0 comments omg y we have to calculate dr^(10000000007-2),it will be such a huge number

mjarun777 + 1 comment dr^1000000005 will take lot of time to complete how to avoid that

pasupuletiganes1 + 0 comments do fast exponentiation

yogesh_gawade010 + 0 comments (Nr * Dr -1 ) % P = ((Nr % P) * (Dr^-1 % P)) % P, is not correct equation. (Dr^(p-1))%p = 1(a^(p-1)-1 is divisible by p) ((Nr * Dr^-1 ) % P)*(Dr^(p-1))%p) = (Dr^(p-1))%p*1 (Dr^(p-1))%p = ((Nr * Dr^-1 ) % P)*(Dr^(p-1))%p)%p = (Nr*Dr^(-1)*Dr^(p-1))%p =(Nr*Dr*(p-2))%p

CollinJakubik + 0 comments [deleted]1616410257_cs3e + 0 comments m * factorial(m+n-1) / factorial(m)*factorial(n) what is the problem with this problem?? please explain this??

ashwinkumare994 + 0 comments Normally i want to tell you to Join this game platform.Board game is most famous for his trick taking advantages and many of the people enjoying so much bejeweled 3 free online and am also ready to join and play every time.

bazuka_ + 3 comments finally solved after one month.

raj_yadav29oct + 3 comments Bro i am getting run time error on my c# code can you help me with that-

static void Main(string[] args) { int t =Convert.ToInt32(Console.ReadLine()); while(t>0) { string[] data =Console.ReadLine().Split(' '); ulong[] data1 = Array.ConvertAll(data, ulong.Parse); ulong N = data1[0]; ulong M = data1[1]; ulong newM = M - 1; ulong topfact = 1; ulong belowfact1 = 1; ulong belowfact2 = 1; ulong result = 0; for (ulong i=1;i<=(N+ newM);i++) { topfact = topfact * i; if(i<=N) { belowfact1 = (belowfact1 * i); } if (i <= newM) { belowfact2 = belowfact2 * i; } } result = (topfact / (belowfact1 * belowfact2))%1000000007; Console.WriteLine(result); t--; } Console.Read(); }

bazuka_ + 1 comment Actually the answer is

(m+n-1)C(n)=(m+n-1)!/ ((m-1)!)*n!)

and the forumula

Ncr=(n-1)c(r-1)+ (n-1)c(r)

now you can apply dp you may take help of this function as it is little bit tuff for me to understand c# that's why iam writing this function

`cpp

for (i = 0; i <= n; i++) { for (j = 0; j <= k; j++) {

`if (j == 0 || j == i)//as nc0=ncn=1; C[i][j] = 1; else C[i][j] = ((C[i-1][j-1])%mod +( C[i-1][j])%mod)%mod; } }`

`

now you can return the desired answer .

Now in your code this line

result = (topfact / (belowfact1 * belowfact2))%1000000007; will get run-time error or tle as your modulus approach formula is not correct as

(a * b) % mod = ((a % mod) * (b % mod)) % mod, (a / b ) % mod = ((a % mod) * (b^-1 % mod)) % mod,

and one more reason is that the

(topfact / (belowfact1*belowfact2))

will not work properly .

if problem persist then feel free to contact for further

clarification or you may take help of my c code

....

tamim447 + 0 comments k means m..?

vishu006 + 0 comments Hey take a look at this if it helps

from math import factorial n=int(raw_input()) for i in range(n): a,b=map(int,raw_input().split()) print (factorial(a+b-1)/(factorial(a)*factorial(b-1)))%1000000007

g_sosacuervo1 + 0 comments I believe if you try with N=1000 and M=1000, you will get the run time error. Basically, 1000!*999>ulong.MAX, in other words, it should give you kind of overflow.

Mohit_Yadav_389 + 0 comments Nice!

rejwancse10 + 1 comment will you please make me understand the logic of the problem?

codedeepesh + 0 comments logic is simple there are total m 1's and n 0's now you fix one 1 at starting of the string so you have m-1 1's now we have arrange them m+n-1!/(m-1!)(n!)

NiCkSs + 2 comments Compact Python 3 solution with built-in pow (performing modular exponentiation) and factorial.

import math q=int(input()) P=10**9+7 for _ in range(q): [n,m]=list(map(int,input().split())) m=m-1 num=math.factorial(n+m)%P den=math.factorial(n)*math.factorial(m) den=pow(den,P-2,P) print((num*den)%P)

adarshdubey1998 + 0 comments Thanks for this

phillm6 + 0 comments Thank you. I was wondering how to speed this up, I hadn't even thought of built in pow to get the modulo inverse of the denominator.

LINKONRUHUL + 2 comments I think this code is better than the editorial code to understand! First, calculate all combinations from 1 to 2000 using this fromula

**(ncR=(n-1)c(R-1)+(n-1)cR)**.Then just find the appropriate result according to the problem satement!#include <bits/stdc++.h> #define ___ ios_base::sync_with_stdio(false);cin.tie(NULL); #define div 1000000007 using namespace std; int com[2017][2017]; int main() { int n,r,a,b,c; for(n=0; n<=2000; n++) { for(r=0; r<=n; r++) { if(r==0 || r==n) com[n][r]=1; else com[n][r]=(com[n-1][r-1]+com[n-1][r])%1000000007; } } cin>>c; while(c--) { cin>>a>>b; cout<<com[a+b-1][b-1]<<endl; } return 0; }

mjarun777 + 0 comments do u think its easy to find 4M values

rejwancse10 + 0 comments for(n=0; n<=2000; n++) { for(r=0; r<=n; r++) { if(r==0 || r==n) com[n][r]=1; else com[n][r]=(com[n-1][r-1]+com[n-1][r])%1000000007; } }

`i am not getting why this two loops are being used sir will you please make me understnad with example?`

aayush_break + 1 comment It took me a while to understand the logic , but there's a catch in the problem and it's not that hard to simplify it...

fo eg: string x=11100 for the string to start from 1, just fix the position of one of the ones(1s), hence you get

`(1) (1100)`

now we need to find possible combinations from those 4 string digits since we have already fixed the '1' hence,

`(4)c(noOfZeroes)= 4!/2!(4-2)!=6(ans)`

That's all, i did it in java so i used BigInteger for calc.

ebrucecfa + 0 comments Perfect example of why one should not commence coding too soon. I took my dog for a nice walk while thinking about this problem. This idea came too me pretty quickly.

- Read inputs.
- Grab getFactorial method that uses BigInteger.
- Write getCominations method.
- Write output for ea test case.

Below are some helpful Java methods

public static BigInteger getFactorial(int num) { BigInteger result = BigInteger.ONE; for (int i = 1; i <= num; i++) result = result.multiply(BigInteger.valueOf(i)); return result; } // getFactorial public static BigInteger getCombinations(int numTotal, int numZeros) { BigInteger result = BigInteger.ONE; BigInteger modulo = BigInteger.valueOf(1000000007); result = getFactorial(numTotal).divide((getFactorial(numZeros).multiply(getFactorial(numTotal-numZeros)))); return result.remainder(modulo); } // getCombinations

Sort 104 Discussions, By:

Please Login in order to post a comment