## Sherlock and Permutations

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

....

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!

- R
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!)

VamsiSangam + 14 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 + 2 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)`

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

- RS
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

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.

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

- MK
mihirkarkare + 1 comment 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; }`

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

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

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

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

- GP
pasupuletiganes1 + 0 comments do fast exponentiation

- YG
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

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

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

- R
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

codedeepesh + 0 comments I don't know why this problem is marked as hard??

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

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)

- TD
tordjarv + 0 comments The only problem with this one (and with the matrix tracing problem) where to find a fast and exact algorithm for large modular binomial coefficients. I suspect that there are many other problems here that requires this. Took me a while to find one, but I realized that I could use Fermat's little theorem to compute the modular division (1000000007 is prime) needed for the binomial coefficient.

julie_larson + 0 comments I am unable to make a reply comment, so I'll repost up here at the top

In response to vishu006 who said:

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

This works, but I don't quite understand because this is just the straight formula for permutation of multisets, right? https://en.wikipedia.org/wiki/Permutation#Permutations_of_multisets

How do you determine what percentage of the resulting set begins with a 1?

It seems like that requirement isn't being met?

sz_andras_91 + 0 comments **python 2**def f(n): return reduce(lambda x, y : x * y, [1] + range(1, n+1)) for _ in range(int(raw_input())): a, b = map(int, raw_input().split()) print (f(a + b - 1) // (f(a) * f(b - 1))) % 1000000007

- DM
d_mirauta + 0 comments Just thought I should mention, if you did the Matrix Traversal question, this is basically the same thing. Matrix traversal boiled down to the number of combinations of "move-up" actions and "move-right" actions. Now we want the total number of combinations of 0's and 1's in the string resulting from ignoring the first element. First item is fixed to 1, as we are uninterested in the other case, so the answer is choose(m-1,m+n-1). In the Matrix question the answer was choose(m-1,m+n-2), so you need only make a small change to your old code.

Sort 61 Discussions, By:

Please Login in order to post a comment