You have an array A of n integers. You can choose some element in the array and multiply it by -1. You have to do this operation total K times. Find the number of different arrays you can end up with.
QUICK EXPLANATION:
The basic idea of the problem is to choose some elements in the array and multiply by -1’s. Remaining operations can be done on a single element by making sure that its parity is not changed. If there exists a zero element in the array, the remaining operations can always be done on that element. In this case, the condition of making sure parity is unchanged is implicitly satisfied.
EXPLANATION:
Notice that the elements of the final array will be either same, or multiplied by -1. This means, that we can replace each number in the array with 0 (if the element is zero), 1 (if the element is positive), -1 (if it is negative).
The basic idea of the problem is to choose some elements in the array and multiply by -1’s. Remaining operations can be done on a single element by making sure that its parity is not changed. If there exists a zero element in the array, the remaining operations can always be done on that element. In this case, the condition of making sure parity is unchanged is implicitly satisfied.
So, we will check whether we can change only some x non-zero elements. If there exists a zero element in the array, then it can always be done. Otherwise, if K - x is even, then also it can be done by applying the operation on same element multiple times. Number of ways of choosing x elements out n elements is denoted by C(n, k) which can be found by precomputing factorials and finding inverse modulo a number.
Time Complexity:
\mathcal{O}(n) or \mathcal{O}(n \, log n) if you are finding inverse modulo in each call of C(n, k)
I think it is due to calling combination function for each iteration in which you compute factorial upto n again again instead of storing it. If you store factorial upto 100000 in an array in main() before while(t–) and use it for each call to combination function then it would certainly passed.
@ohmankur, your code is probably TLEing cause you are calculating the vector “f”, for maintaining factorials, each time you are calling your “C” function to given nCr. You can instead, precompute factorials upto 10^5 and store them in “f” for once, instead repeatedly calculating them.
Have a look at my code to understand more clearly and see where I have calculated array “f”.
@easy_ It might be possible that when you calculate nChoosek it might get big enough than what unsigned long long int can store, though not sure, and may when you do this in loops ans+=nCr(i) -> I think here also there are chances that it might be overflowing.
Maybe make some changes there and it might work!
@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.
@devilhector your code fails on the cases when there is 0 present in the array
for eg. n=5,k=5,array=[1,2,3,0,0]
check this actual answer will be 8,but your code outputs 4.
can anyone tell me why code fails for higher numbers…it is giving correct answer but dont no why i am getting only 40 marks.
pleas tell me. https://www.codechef.com/viewsolution/10347950