Recently ,in educational round 83. In question D , i deduced a formula
for(i=n-1;i<=m;i++) { ans=ans+((nCr(i-1,n-2,mod))%mod; } And after that ans=(ans*pow(2,n-3,mod)*(n-2))%mod;
After looking for correct solution i found correct ans was nCr(m,n-1)*(n-2)*pow(2,n-3).
But later observe that for smaller test case my formula was working ,but giving Tle ,at larger tc.
So it that means expression nCr(m,n-1,mod) is equal to summation of nCr(i-1,n-2,mod) ; i range[n-1,m] .
If it is so ,can anyone help me to prove it..
here is my solution link 72867206
It gave TLE because you implemented that wrong. Have a look at my solution here
I have implemented the same logic and got AC
Do i need to precalculate ,factorials and inverse modulus?? What part of my code is wrong?? , i designed code to calculate Combination using lucas concept? And later used fast power to calculate power.. , Any other suggesion ??...
Yes you need to precalculate. You are calculating inverse modulus from 1 to r for every iteration where r = n — 2. So your complexity is m*n and hence the TLE