@prak_blah Yes. This is the case when there is no zero in the array. If there are say p zeroes then make n -= p
and add up nC0, nC1, nC2, …nCk.(if(k > n) make k = n).
And do anyone know how to comment on answer instead of writing another one?
https://www.codechef.com/viewsolution/10412867
why did this solution get tle in the final subtask?
I was calculating the sum of alternating binomial coefficients and this ncr function seems to be good.
plz help
CodeChef: Practical coding for everyone I am unable to find the mistake in my solution. I hope I have made a subtle one. Any help is appreciated.
hat is wrong with my code if only subtask one is considered?? the third task in subtask 1 showed wrong answer?? rest other were correct…
hat is wrong with my code if only subtask one is considered?? the third task in subtask 1 showed wrong answer?? rest other were correct…
Hi! I tried a different approach , I followed this stack overflow answer and implemented it. However its failing on just 3 subtasks. I have been trying to find out why for the past few days. Can anyone help me debug? 
https://www.codechef.com/viewsolution/10410059
EDIT: I managed to get an AC with this approach. My inverse modulo was wrong.
your nChoosek function is overflowing
Precompute the values of factorials % MOD and use them,dont repeatedly calculate them as u are doing here…
@easy_ you can store factorials up to n using for loop and taking mod 1000000007 in each step. To divide by k! and ***(n - k)!***, use modulo-inverse. Modulo-inverse can be calculated by fast binary exponentiation, used to calculate ***k ^ (MOD - 2)***.
long long fastpower(long long base, long long index) {
long long res = 1;
while(index) {
if(index & 1) res = (res * base) % MOD;
base = (base * base) % MOD;
index >>= 1;
}
return res % MOD;
}
To calculate modulo-inverse just pass k as base and (MOD - 2) as index. Remember, this works only if base and MOD are co-prime. This is proved by Fermat’s Little Theorem.
@amit_369 Just a couple of suggestions:
- change data-type int to long long. There might be overflow problem.
- instead of dividing, using modulo-inverse of that number
What is wrong with my code if only subtask one is considered?? the third task in subtask 1 showed wrong answer??
rest other were correct…
you should precompute all factorials upto 100000 before hand so that u dont have recompute them again and again