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
Yeah! I got that thanx
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
Can anybody tell me why I am getting WA
https://www.codechef.com/viewsolution/32375114
I have applied a same approach.
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
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
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.
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.
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
Upper negation looks really nice, heard of that first time…
After reading the editorial the first question arises is what is NTT ?
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
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.
Assume all -1 s are in your sequence by default. Your current sum is -q. Take the set of all 1 s and -1 s. If you choose a 1, you add it to your sequence, and if you choose a -1, you remove it. Now since both actions add 1 to your total sum, you need to choose q+k to get the sum to k
1 Like
Another DP alternative : Share a method to find the multiplicative inverse of 1~n mod p - Codeforces ,
Modular Inverse - Algorithms for Competitive Programming
I got the tutorial’s first and second part. I read the FFT but unable to find good( easy from scratch) resources for NTT. Please help if anyone knows. I am having problem with primitive root and concept when read from cp-algorithms and codeforces tutorial. If any easier site then it will be very helpful!
This is a very awesome method. Thanks for sharing here.