We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

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 ^{-1}' term and the equation becomes,

(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 ^{(P - 2)} % P) can be calculated by using the technique stated in the link provided by the editorial.

But the problem is, that 'Dr' over there, itself can be very big. We have techniques to calculate 'x ^{y} % P', but in our case this '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 ^{(P - 2)} % P) .....?? 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...! :-)

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...! :-)

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) {

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

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!'....??

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

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.

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)

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.

## Sherlock and Permutations

You are viewing a single comment's thread. Return to all 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}) % PNow 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)) % PNow, 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)) % PNow, calculating

(Nr % P)is simple, we use the above used modular arithematic principle, and the term(Drcan 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}% Px' 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)Ohh dear!

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...! :-)

So, in our next step we need the help of

higher powers, or we need to calculateab %m.Suppose we need to calculate

2100 % 11.Now popping whole stack,

thank you very much,it works!

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

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:

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

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!'....??You need to calculate factorials using method posted in first reply.

Now problem reduces to

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

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

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

Exactly.

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

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.

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.

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

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

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

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)

can you please explain the logic behind replacing Dr^(-1) with Dr^(p-2)??

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

dr^1000000005 will take lot of time to complete how to avoid that

do fast exponentiation

(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

m * factorial(m+n-1) / factorial(m)*factorial(n) what is the problem with this problem?? please explain this??

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.