# Sherlock and Permutations

# Sherlock and Permutations

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

+ 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; }

+ 3 comments finally solved after one month.

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

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

Sort 131 Discussions, By:

Please Login in order to post a comment