RECNDSUB - Editorial

editorial
, , , , , ,
7

I cannot recall any questions which use this identity but googling “codechef vandermonde’s identity” revealed that GMEDIAN’s editorial mentioned this identity.

2 Likes
9

Hey! I have a doubt. The limit of i in summation ranges from 0 to min(cnt1-k,cnt-1) if i am not wrong. So my question is wont it effect the identity? bcz in identity upper limit is necessarily needed to be cnt1-k

2 Likes
10

@m0nk3ydluffy Just for curiosity, what came to your mind before applying nCr = nCn-r identity, cause I was stuck on that step and I wanted a closed-form of summation but I was not able to get it. Maybe because I had never used Vandermonde’s Identity before, but after reading Wikipedia article I feel this identity is very intuitive especially after reading combinatorial proof in the given article. So what are your thoughts, what should we do in such cases?

11

Value of nCr is zero when r<0 or r>n. This fact preserves the mathematical soundness of all combinatorial identities. So you could very well change the range of i in that summation, it won’t make the identity incorrect :slight_smile: .

3 Likes
12

Oh yeah i got that thanx!

13

Hey!. As @anon49376339 said, we generally define binomial coefficient \binom{n}{m} to be equal to zero if m is not in the valid range (valid range being 0 <= m <= n). So we do not have to care about the upper bound in the identity (hence I did not specify any upper bound in the summation). In fact, the identity would be valid even if we sum over all the integers in [-\infin, \infin] (as we have defined the binomial coefficient to be zero for negative m)

1 Like
14

Hey! I guess you mean “nCr = nC(n - r) identity”. You can read https://trans4mind.com/personal_development/mathematics/series/summingBinomialCoefficients.htm. It has some interesting tricks which might be helpful in the future.

2 Likes
15

Yeah! I got that thanx

16

If anyone was wondering about primitive roots for NTT, I found some to be 18 for 2^21, and 55 for 2^22

2 Likes
18

@m0nk3ydluffy Yes , my bad !

19

Can anybody tell me why I am getting WA
https://www.codechef.com/viewsolution/32375114
I have applied a same approach.

21

I used same approach as you but with modulo inverse. Can you tell me how to speed up the solution, my solution passed but took around 1 second. I stored factorials upto 1e5 and modinverse of factorials upto 1e5. I guess complexity of precomputation should be O(N\log(P)) where P is the prime, and complexity in finding answer will be O(N) still it takes 1000ms.

How should I improve complexity, I suppose the computation of moduloinverse is taking a lot of time.

Here is submission: CodeChef: Practical coding for everyone

22

You can precompute in O(n + \log(p))
If you understand modular arithmetic, why this works should be obvious.

vector<ll> fact;
vector<ll> invfact;
void computefactorial(int n){
    fact.resize(n);
    invfact.resize(n);
    fact[0]=1;
    for(int i=1;i<n;i++){
        fact[i]=i*fact[i-1];
        fact[i]%=p;
    }
    invfact[n-1]=modpower(fact[n-1],p-2);
    for(int i=n-2;i>=0;i--){
        invfact[i]=(i+1)*invfact[i+1];
        invfact[i]%=p;
    }
}
1 Like
23

Multiply those polynomials and write down the coefficient of x^K in the product,
[(1+x)^(p+q)]/[x^q].
This coefficient will be the same as the summation of terms above.

24

Oh my god how I missed this, going in reverse! So we only need one call to binary_exp. Thanks for eye opener

Now I am getting 320ms, much improved than 1000ms earlier.

26

https://www.codechef.com/viewsolution/32390270
Please view my solution what i have done is that i have counted -1,0,1 and then multiply the combination of all there sets .
But giving me tle so what should i do please tell

27

Upper negation looks really nice, heard of that first time…

28

After reading the editorial the first question arises is what is NTT ?

29

Number theoretic transform. It’s an overkill here, but it’s a very useful concept for multipliying polynomials modulo p. There are some additional constraints on p, but you’ll figure it out.

I’d recommend starting with fast fourier transform, which is just for multiplying polynomials.

3 Likes
30

without seeing derivation (p+q)C(q+k) sounds like choosing (q+k) items from all 1’s and -1’s ,How does it even looks correct int his manner please Elaborate.