# 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 + 0 comments 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

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 + 1 comment 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 :)

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 + 0 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)

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

superadirockz + 3 comments Python

def solve(n, m): k=math.factorial(n+m-1) a=math.factorial(n)*math.factorial(m-1) k=k//a return (k%1000000007)

swtchaudhari490 + 0 comments Thank you so much!!

sravaniteja + 1 comment def fact(a): p=1 if(a==0): return p; else: while(a!=0): p = p*a a = a-1 return p t = int(input()) for i in range(t): m,n = map(int,input().strip().split()) print((int(fact(m+n-1)/(fact(m)*fact(n-1))))%(1000000007))

whats wrong in this code?

superadirockz + 1 comment use integer divison '//' in place of '/' in 'fact(m+n-1)/(fact(m)*fact(n-1))'

sravaniteja + 0 comments Thank you

nickbaxter883 + 0 comments Wow I simply assumed the numbers would get too large for that to work. Python is awesome! I know it automatically resizes ints to longs. I guess it does that for BigInts too. On harder challenges I'd be careful about timeout, but this looks like a much cleaner solution if the judge will run it. Much cleaner than the Python solution I posted!

HaltingProblem + 0 comments You may be really unhappy trying to figure this out by yourself, but mathematicians have already done so for you.

If I'm not mistaken. It's an example of what they call a k-multicombination. There are similar such formulas for counting different kinds of problems.

https://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition

See VamsiSangam's answer for the formula that the 'double parentheses' notation is referring to.

import math # Complete the solve function below. def solve(n, m): P=10**9+7 m=m-1 num=math.factorial(n+m)%P den=math.factorial(n)*math.factorial(m) den=pow(den,P-2,P) return ((num*den)%P)

kingjoe251 + 0 comments Woah! This problem looks insane! I might seek again for some experts in customessaymeister.com site to solve this one. As I've received an A- paper last time I had their service for a narrative essay. I am confident enough that they will also provide me a top notch paper again even with Mathematics papers or problems in the near future. Hope this will help you as well. Good day folks!

-JK

samsonw260 + 1 comment this is my code enclosed below it seems to work for all test cases yet the editor is not accepting it on account of runtime error can somebody please suggest any edits to it

# include

using namespace std; int factorial(int a) { if(a==0||a==1) { return 1; } else{ return a*factorial (a-1); }

} int main() { int n,m; cin>>n>>m; int ans=(factorial(n+m))/(factorial(m)*factorial(n)); int ans1=(factorial(m+m-1))/(factorial(n-1)*factorial(m)); int final_ans=ans-ans1; cout<

Shu7bh + 0 comments Probably the stack is having an overflow. And also the num can get very big. Eg 500! is like greater than 10^1000. And integers can handle numbers till 10^9.

Also, you have to return the answer in the form of ans % 10^9 + 7

sohamthehighbrow + 0 comments def solve(n, m):

`return int(math.factorial(n+m-1)//(math.factorial(m-1)*math.factorial(n)))%(10**9+7)`

Sort 86 Discussions, By:

Please Login in order to post a comment