@nishant10 Taking absolute value will not always work. For example -16%5 is 4, taking absolute value gives 1. You can use @vishfrnds approach for negative numbers or find (A[j]%m) as ((A[j]%m)+m)%m (this works fine for both positive and negative numbers)
oh sorry that was a mistake
now its correct …
Then what is the value of i while calculating summation
“i” will go from 1 to M-1
dp[0][0] = 2^count[0]
dp[0][j] = 0
or If you want to run “i” from 0 to M-1 then
dp[-1][0] = 1
dp[-1][j] = 0
The complexity of finding summation is O(N), which is done O(M) times as you said, so isn’t the overall complexity O(MN)
No that loop will run for count[i] time for each i
and i varying from 1 to M-1
so in total it’ll run sigma(count[i]) times
which is O(N)
1 Like
Ok, got it, Thanks a lot
yeah choose(n,k) % P can be calculated in O(1) with some pre computation
precomputate fact[i] array which is (i!)%P
and ifact[i] array which is Modular multiplicative inverse of i! modulo P
then choose(n,k)%P = (fact[n]*ifact[n-k]*ifact[k])%P
precomputation of these arrays can be done in in O(NlogP)
1 Like
Thanks! That seemed quite straight forward (in the sense that this is how we naturally calculate choose n,k (using the formula)). So we can compute nck with just O(n) pre-computation (with an extra logP for inverse calculation :))
My solution is basically the first solution presented in the editorial (the one that should supposedly time out).
ok.Thanks.
Can you please explain this. As choose(count[i],k1) and choose(count[i],k2) can go to indices in the summation array and later on get added up while filling up the dp[I][J] array. So how can we make sure that k1 + k2 has a size less than the total size of count[i] ?
Yes, per query the complexity is O(N + MMM)
We actually do it in order. We have M classes of numbers. We start from class 0 and go till class M-1, at each class we decide on how many numbers we need to take from that class, we also need the remainder when we move to next state.
We move from state DP[i][carry] to DP[i+1][NewCarry], where i is the class and carry is the current sum modulo M
Give me link. I will see.
Also note that Modulo operator is very costly and so excessive use might have resulted in TLE.
1 Like
plz help …