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.