Sort 115 Discussions, By:
Please Login in order to post a comment
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 (109 + 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...! :-)
finally solved after one month.
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!
#define ___ ios_base::sync_with_stdio(false);cin.tie(NULL);
#define div 1000000007
using namespace std;
for(n=0; n<=2000; n++)
for(r=0; r<=n; r++)
if(r==0 || r==n)
Compact Python 3 solution with built-in pow (performing modular exponentiation) and factorial.
for _ in range(q):
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
now we need to find possible combinations from those 4 string digits since we have already fixed the '1'
That's all, i did it in java so i used BigInteger for calc.